1use crate::models::decision::Decision;
7use crate::models::graph::{HamiltonianCircuit, MinimumVertexCover};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::traits::Problem;
12use std::collections::BTreeSet;
13
14#[derive(Debug, Clone)]
15enum ConstructionKind {
16 FixedYes { source_cover: Vec<bool> },
17 FixedNo,
18 Theorem(TheoremConstruction),
19}
20
21#[derive(Debug, Clone)]
22struct TheoremConstruction {
23 num_source_vertices: usize,
24 selector_count: usize,
25 edges: Vec<(usize, usize)>,
26 incident_edges: Vec<Vec<usize>>,
27}
28
29impl TheoremConstruction {
30 fn active_vertices(&self) -> impl Iterator<Item = usize> + '_ {
31 self.incident_edges
32 .iter()
33 .enumerate()
34 .filter(|(_, edges)| !edges.is_empty())
35 .map(|(v, _)| v)
36 }
37
38 fn gadget_base(&self, edge_idx: usize) -> usize {
39 self.selector_count + 12 * edge_idx
40 }
41
42 fn gadget_vertex(&self, edge_idx: usize, vertex: usize, position: usize) -> usize {
43 let (u, v) = self.edges[edge_idx];
44 let side = if vertex == u {
45 0
46 } else if vertex == v {
47 1
48 } else {
49 panic!(
50 "vertex {vertex} is not incident on edge {:?}",
51 self.edges[edge_idx]
52 );
53 };
54
55 self.gadget_base(edge_idx) + side * 6 + (position - 1)
56 }
57
58 fn path_endpoints(&self, vertex: usize) -> Option<(usize, usize)> {
59 let incident = self.incident_edges.get(vertex)?;
60 let first = *incident.first()?;
61 let last = *incident.last()?;
62 Some((
63 self.gadget_vertex(first, vertex, 1),
64 self.gadget_vertex(last, vertex, 6),
65 ))
66 }
67
68 fn covers_all_edges(&self, selected: &[bool]) -> bool {
69 self.edges
70 .iter()
71 .all(|&(u, v)| selected.get(u) == Some(&true) || selected.get(v) == Some(&true))
72 }
73
74 #[cfg(any(test, feature = "example-db"))]
75 fn exact_selected_vertices(&self, source_cover: &[bool]) -> Option<Vec<usize>> {
76 if source_cover.len() != self.num_source_vertices || !self.covers_all_edges(source_cover) {
77 return None;
78 }
79
80 let mut selected: Vec<usize> = self
81 .active_vertices()
82 .filter(|&v| source_cover[v])
83 .collect();
84
85 if selected.len() > self.selector_count {
86 return None;
87 }
88
89 for v in self.active_vertices() {
90 if selected.len() == self.selector_count {
91 break;
92 }
93 if !source_cover[v] {
94 selected.push(v);
95 }
96 }
97
98 (selected.len() == self.selector_count).then_some(selected)
99 }
100
101 #[cfg(any(test, feature = "example-db"))]
102 fn gadget_segment(
103 &self,
104 edge_idx: usize,
105 vertex: usize,
106 selected_exact: &BTreeSet<usize>,
107 ) -> Vec<usize> {
108 let (u, v) = self.edges[edge_idx];
109 let other = if vertex == u {
110 v
111 } else if vertex == v {
112 u
113 } else {
114 panic!(
115 "vertex {vertex} is not incident on edge {:?}",
116 self.edges[edge_idx]
117 );
118 };
119
120 if selected_exact.contains(&other) {
121 return (1..=6)
122 .map(|position| self.gadget_vertex(edge_idx, vertex, position))
123 .collect();
124 }
125
126 if vertex == u {
127 vec![
128 self.gadget_vertex(edge_idx, u, 1),
129 self.gadget_vertex(edge_idx, u, 2),
130 self.gadget_vertex(edge_idx, u, 3),
131 self.gadget_vertex(edge_idx, v, 1),
132 self.gadget_vertex(edge_idx, v, 2),
133 self.gadget_vertex(edge_idx, v, 3),
134 self.gadget_vertex(edge_idx, v, 4),
135 self.gadget_vertex(edge_idx, v, 5),
136 self.gadget_vertex(edge_idx, v, 6),
137 self.gadget_vertex(edge_idx, u, 4),
138 self.gadget_vertex(edge_idx, u, 5),
139 self.gadget_vertex(edge_idx, u, 6),
140 ]
141 } else {
142 vec![
143 self.gadget_vertex(edge_idx, v, 1),
144 self.gadget_vertex(edge_idx, v, 2),
145 self.gadget_vertex(edge_idx, v, 3),
146 self.gadget_vertex(edge_idx, u, 1),
147 self.gadget_vertex(edge_idx, u, 2),
148 self.gadget_vertex(edge_idx, u, 3),
149 self.gadget_vertex(edge_idx, u, 4),
150 self.gadget_vertex(edge_idx, u, 5),
151 self.gadget_vertex(edge_idx, u, 6),
152 self.gadget_vertex(edge_idx, v, 4),
153 self.gadget_vertex(edge_idx, v, 5),
154 self.gadget_vertex(edge_idx, v, 6),
155 ]
156 }
157 }
158
159 #[cfg(any(test, feature = "example-db"))]
160 fn vertex_path(&self, vertex: usize, selected_exact: &BTreeSet<usize>) -> Vec<usize> {
161 let mut path = Vec::new();
162 for &edge_idx in &self.incident_edges[vertex] {
163 path.extend(self.gadget_segment(edge_idx, vertex, selected_exact));
164 }
165 path
166 }
167
168 #[cfg(any(test, feature = "example-db"))]
169 fn build_target_witness(&self, source_cover: &[bool]) -> Vec<usize> {
170 let Some(selected_vertices) = self.exact_selected_vertices(source_cover) else {
171 return Vec::new();
172 };
173
174 let selected_exact: BTreeSet<usize> = selected_vertices.iter().copied().collect();
175 let mut witness = Vec::with_capacity(self.selector_count + 12 * self.edges.len());
176
177 for (selector, &vertex) in selected_vertices.iter().enumerate() {
178 witness.push(selector);
179 witness.extend(self.vertex_path(vertex, &selected_exact));
180 }
181
182 witness
183 }
184
185 fn decode_solution(
186 &self,
187 target_problem: &HamiltonianCircuit<SimpleGraph>,
188 target_solution: &Vec<usize>,
189 ) -> crate::rules::ExtractionResult<Vec<bool>> {
190 Ok({
191 let mut source_cover = vec![false; self.num_source_vertices];
192 if !target_problem.evaluate(target_solution)?.0 {
193 return Err(crate::rules::ExtractionError::invalid(
194 "target configuration is not a Hamiltonian circuit",
195 ));
196 }
197
198 let mut positions = vec![usize::MAX; target_solution.len()];
199 for (idx, &vertex) in target_solution.iter().enumerate() {
200 if vertex >= positions.len() || positions[vertex] != usize::MAX {
201 return Err(crate::rules::ExtractionError::invalid(
202 "target circuit contains an invalid or repeated vertex",
203 ));
204 }
205 positions[vertex] = idx;
206 }
207
208 let len = target_solution.len();
209 let touches_selector = |vertex: usize| {
210 let idx = positions[vertex];
211 let prev = target_solution[(idx + len - 1) % len];
212 let next = target_solution[(idx + 1) % len];
213 prev < self.selector_count || next < self.selector_count
214 };
215
216 for vertex in self.active_vertices() {
217 let Some((start, end)) = self.path_endpoints(vertex) else {
218 continue;
219 };
220 if touches_selector(start) && touches_selector(end) {
221 source_cover[vertex] = true;
222 }
223 }
224
225 let selected_count = source_cover.iter().filter(|&&x| x).count();
226 if selected_count != self.selector_count || !self.covers_all_edges(&source_cover) {
227 return Err(crate::rules::ExtractionError::invalid(
228 "target circuit does not encode a source vertex cover of the required size",
229 ));
230 }
231
232 source_cover
233 })
234 }
235}
236
237#[derive(Debug, Clone)]
240pub struct ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
241 target: HamiltonianCircuit<SimpleGraph>,
242 construction: ConstructionKind,
243}
244
245impl ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
246 #[cfg(any(test, feature = "example-db"))]
247 fn build_target_witness(&self, source_cover: &[bool]) -> Vec<usize> {
248 match &self.construction {
249 ConstructionKind::FixedYes { .. } => vec![0, 1, 2],
250 ConstructionKind::FixedNo => Vec::new(),
251 ConstructionKind::Theorem(construction) => {
252 construction.build_target_witness(source_cover)
253 }
254 }
255 }
256}
257
258impl ReductionResult for ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
259 type Source = Decision<MinimumVertexCover<SimpleGraph, i64>>;
260 type Target = HamiltonianCircuit<SimpleGraph>;
261
262 fn target_problem(&self) -> &Self::Target {
263 &self.target
264 }
265
266 fn extract_solution(
267 &self,
268 target_solution: &<Self::Target as crate::traits::Problem>::Solution,
269 ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
270 crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
271
272 Ok({
273 match &self.construction {
274 ConstructionKind::FixedYes { source_cover } => {
275 if self.target.evaluate(target_solution)?.0 {
276 source_cover.clone()
277 } else {
278 return Err(crate::rules::ExtractionError::invalid(
279 "target configuration is not the fixed Hamiltonian circuit",
280 ));
281 }
282 }
283 ConstructionKind::FixedNo => {
284 return Err(crate::rules::ExtractionError::invalid(
285 "the fixed negative target instance has no extractable witness",
286 ))
287 }
288 ConstructionKind::Theorem(construction) => {
289 construction.decode_solution(&self.target, target_solution)?
290 }
291 }
292 })
293 }
294}
295
296fn normalize_edges(edges: Vec<(usize, usize)>) -> Vec<(usize, usize)> {
297 let mut normalized: Vec<_> = edges
298 .into_iter()
299 .map(|(u, v)| if u < v { (u, v) } else { (v, u) })
300 .collect();
301 normalized.sort_unstable();
302 normalized
303}
304
305fn insert_edge(edges: &mut BTreeSet<(usize, usize)>, a: usize, b: usize) {
306 let edge = if a < b { (a, b) } else { (b, a) };
307 edges.insert(edge);
308}
309
310#[reduction(
311 transform = unavailable {
312 num_vertices = "the construction size depends on the decision threshold, which is not a problem parameter",
313 num_edges = "the construction size depends on the decision threshold, which is not a problem parameter",
314 }
315)]
316impl ReduceTo<HamiltonianCircuit<SimpleGraph>> for Decision<MinimumVertexCover<SimpleGraph, i64>> {
317 type Result = ReductionDecisionMinimumVertexCoverToHamiltonianCircuit;
318
319 fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
320 let weights = self.inner().weights();
321 if weights.iter().any(|&weight| weight != 1) {
322 return Err(crate::rules::ReductionError::invalid_target::<
323 Decision<MinimumVertexCover<SimpleGraph, i64>>,
324 HamiltonianCircuit<SimpleGraph>,
325 >(
326 "Garey-Johnson construction requires unit vertex weights"
327 ));
328 }
329
330 let num_source_vertices = self.inner().graph().num_vertices();
331 let raw_bound = *self.bound();
332 if raw_bound < 0 {
333 return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
334 target: HamiltonianCircuit::new(SimpleGraph::path(3)),
335 construction: ConstructionKind::FixedNo,
336 });
337 }
338
339 let k = self.k();
340 let edges = normalize_edges(self.inner().graph().edges());
341 let mut incident_edges = vec![Vec::new(); num_source_vertices];
342 for (edge_idx, &(u, v)) in edges.iter().enumerate() {
343 incident_edges[u].push(edge_idx);
344 incident_edges[v].push(edge_idx);
345 }
346
347 let active_vertices: Vec<_> = incident_edges
348 .iter()
349 .enumerate()
350 .filter(|(_, incident)| !incident.is_empty())
351 .map(|(vertex, _)| vertex)
352 .collect();
353 let active_count = active_vertices.len();
354
355 if active_count == 0 || k >= active_count {
356 let mut source_cover = vec![false; num_source_vertices];
357 for vertex in active_vertices {
358 source_cover[vertex] = true;
359 }
360 return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
361 target: HamiltonianCircuit::new(SimpleGraph::cycle(3)),
362 construction: ConstructionKind::FixedYes { source_cover },
363 });
364 }
365
366 if k == 0 {
367 return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
368 target: HamiltonianCircuit::new(SimpleGraph::path(3)),
369 construction: ConstructionKind::FixedNo,
370 });
371 }
372
373 let construction = TheoremConstruction {
374 num_source_vertices,
375 selector_count: k,
376 edges,
377 incident_edges,
378 };
379
380 let mut target_edges = BTreeSet::new();
381 for (edge_idx, &(u, v)) in construction.edges.iter().enumerate() {
382 for position in 1..6 {
383 insert_edge(
384 &mut target_edges,
385 construction.gadget_vertex(edge_idx, u, position),
386 construction.gadget_vertex(edge_idx, u, position + 1),
387 );
388 insert_edge(
389 &mut target_edges,
390 construction.gadget_vertex(edge_idx, v, position),
391 construction.gadget_vertex(edge_idx, v, position + 1),
392 );
393 }
394
395 insert_edge(
396 &mut target_edges,
397 construction.gadget_vertex(edge_idx, u, 3),
398 construction.gadget_vertex(edge_idx, v, 1),
399 );
400 insert_edge(
401 &mut target_edges,
402 construction.gadget_vertex(edge_idx, v, 3),
403 construction.gadget_vertex(edge_idx, u, 1),
404 );
405 insert_edge(
406 &mut target_edges,
407 construction.gadget_vertex(edge_idx, u, 6),
408 construction.gadget_vertex(edge_idx, v, 4),
409 );
410 insert_edge(
411 &mut target_edges,
412 construction.gadget_vertex(edge_idx, v, 6),
413 construction.gadget_vertex(edge_idx, u, 4),
414 );
415 }
416
417 for vertex in construction.active_vertices() {
418 let incident = &construction.incident_edges[vertex];
419 for window in incident.windows(2) {
420 insert_edge(
421 &mut target_edges,
422 construction.gadget_vertex(window[0], vertex, 6),
423 construction.gadget_vertex(window[1], vertex, 1),
424 );
425 }
426
427 let (start, end) = construction.path_endpoints(vertex).ok_or_else(|| {
428 crate::rules::ReductionError::invalid_target::<
429 Decision<MinimumVertexCover<SimpleGraph, i64>>,
430 HamiltonianCircuit<SimpleGraph>,
431 >("active source vertex has no Hamiltonian gadget path endpoints")
432 })?;
433 for selector in 0..construction.selector_count {
434 insert_edge(&mut target_edges, selector, start);
435 insert_edge(&mut target_edges, selector, end);
436 }
437 }
438
439 let target = HamiltonianCircuit::new(SimpleGraph::new(
440 construction.selector_count + 12 * construction.edges.len(),
441 target_edges.into_iter().collect(),
442 ));
443
444 Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
445 target,
446 construction: ConstructionKind::Theorem(construction),
447 })
448 }
449}
450
451#[cfg(feature = "example-db")]
452pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
453 use crate::example_db::specs::assemble_rule_example;
454 use crate::export::SolutionPair;
455
456 vec![crate::example_db::specs::RuleExampleSpec {
457 id: "decisionminimumvertexcover_to_hamiltoniancircuit",
458 build: || {
459 let source = Decision::new(
460 MinimumVertexCover::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1, 1, 1]),
461 1,
462 );
463 let source_config = vec![false, true, false];
464 let reduction = ReduceTo::<HamiltonianCircuit<SimpleGraph>>::reduce_to(&source)
465 .expect("reduction should succeed");
466 let target_config = reduction.build_target_witness(&source_config);
467 assemble_rule_example(
468 &source,
469 reduction.target_problem(),
470 vec![SolutionPair {
471 source_config: serde_json::to_value(source_config)
472 .expect("solution serialization must succeed"),
473 target_config: serde_json::to_value(target_config)
474 .expect("solution serialization must succeed"),
475 }],
476 )
477 },
478 }]
479}
480
481#[cfg(test)]
482#[path = "../unit_tests/rules/decisionminimumvertexcover_hamiltoniancircuit.rs"]
483mod tests;