problemreductions/rules/
hamiltoniancircuit_hamiltonianpath.rs

1//! Reduction from HamiltonianCircuit to HamiltonianPath.
2//!
3//! Given a Hamiltonian Circuit instance G = (V, E) with n vertices, we construct
4//! a Hamiltonian Path instance G' with n + 3 vertices as follows:
5//!
6//! 1. Pick an arbitrary vertex v = 0.
7//! 2. Create a duplicate vertex v' (index n) connected to all neighbors of v.
8//! 3. Add a pendant vertex s (index n+1) with the single edge {s, v}.
9//! 4. Add a pendant vertex t (index n+2) with the single edge {t, v'}.
10//!
11//! G has a Hamiltonian circuit iff G' has a Hamiltonian path (from s to t).
12//!
13//! The target graph G' has n + 3 vertices and m + deg(v) + 2 edges.
14
15use crate::models::graph::{HamiltonianCircuit, HamiltonianPath};
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18use crate::topology::{Graph, SimpleGraph};
19
20/// Result of reducing HamiltonianCircuit to HamiltonianPath.
21///
22/// Stores the target HamiltonianPath instance and the number of original vertices
23/// to enable solution extraction.
24#[derive(Debug, Clone)]
25pub struct ReductionHamiltonianCircuitToHamiltonianPath {
26    target: HamiltonianPath<SimpleGraph>,
27    /// Number of vertices in the original graph.
28    num_original_vertices: usize,
29}
30
31impl ReductionResult for ReductionHamiltonianCircuitToHamiltonianPath {
32    type Source = HamiltonianCircuit<SimpleGraph>;
33    type Target = HamiltonianPath<SimpleGraph>;
34
35    fn target_problem(&self) -> &Self::Target {
36        &self.target
37    }
38
39    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40        let n = self.num_original_vertices;
41        if n == 0 {
42            return vec![];
43        }
44
45        if target_solution.len() != n + 3 {
46            return vec![0; n];
47        }
48
49        let v_prime = n; // index of duplicated vertex v'
50        let s = n + 1; // pendant attached to v=0
51        let t = n + 2; // pendant attached to v'
52
53        // The two pendants force any valid witness to have endpoints s and t.
54        let reversed;
55        let oriented = match (target_solution.first(), target_solution.last()) {
56            (Some(&start), Some(&end)) if start == s && end == t => target_solution,
57            (Some(&start), Some(&end)) if start == t && end == s => {
58                reversed = target_solution.iter().copied().rev().collect::<Vec<_>>();
59                reversed.as_slice()
60            }
61            _ => return vec![0; n],
62        };
63
64        if oriented.get(1) != Some(&0) || oriented.get(n + 1) != Some(&v_prime) {
65            return vec![0; n];
66        }
67
68        oriented[1..=n].to_vec()
69    }
70}
71
72#[reduction(
73    overhead = {
74        num_vertices = "num_vertices + 3",
75        num_edges = "num_edges + num_vertices + 1",
76    }
77)]
78impl ReduceTo<HamiltonianPath<SimpleGraph>> for HamiltonianCircuit<SimpleGraph> {
79    type Result = ReductionHamiltonianCircuitToHamiltonianPath;
80
81    fn reduce_to(&self) -> Self::Result {
82        let n = self.num_vertices();
83
84        // HC is unsatisfiable for n < 3; return a trivially unsatisfiable HP instance.
85        if n < 3 {
86            let target_graph = SimpleGraph::empty(n + 3);
87            let target = HamiltonianPath::new(target_graph);
88            return ReductionHamiltonianCircuitToHamiltonianPath {
89                target,
90                num_original_vertices: n,
91            };
92        }
93
94        let source_graph = self.graph();
95
96        // New vertex indices:
97        // 0..n-1: original vertices
98        // n: v' (duplicate of vertex 0)
99        // n+1: s (pendant of vertex 0)
100        // n+2: t (pendant of v')
101        let v_prime = n;
102        let s = n + 1;
103        let t = n + 2;
104
105        let mut edges: Vec<(usize, usize)> = Vec::new();
106
107        // 1. Copy all original edges
108        for (u, v) in source_graph.edges() {
109            edges.push((u, v));
110        }
111
112        // 2. Connect v' to all neighbors of vertex 0
113        for neighbor in source_graph.neighbors(0) {
114            edges.push((v_prime, neighbor));
115        }
116
117        // 3. Add pendant edge {s, 0}
118        edges.push((s, 0));
119
120        // 4. Add pendant edge {t, v'}
121        edges.push((t, v_prime));
122
123        let target_graph = SimpleGraph::new(n + 3, edges);
124        let target = HamiltonianPath::new(target_graph);
125
126        ReductionHamiltonianCircuitToHamiltonianPath {
127            target,
128            num_original_vertices: n,
129        }
130    }
131}
132
133#[cfg(feature = "example-db")]
134pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
135    use crate::export::SolutionPair;
136
137    vec![crate::example_db::specs::RuleExampleSpec {
138        id: "hamiltoniancircuit_to_hamiltonianpath",
139        build: || {
140            // Square graph (4-cycle): 0-1-2-3-0
141            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
142            crate::example_db::specs::rule_example_with_witness::<_, HamiltonianPath<SimpleGraph>>(
143                source,
144                SolutionPair {
145                    // HC solution: visit vertices in order 0, 1, 2, 3
146                    source_config: vec![0, 1, 2, 3],
147                    // HP solution on G' (7 vertices): s=5, 0, 1, 2, 3, v'=4, t=6
148                    target_config: vec![5, 0, 1, 2, 3, 4, 6],
149                },
150            )
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/hamiltoniancircuit_hamiltonianpath.rs"]
157mod tests;
problemreductions/rules/hamiltoniancircuit_hamiltonianpath.rs

problemreductions/rules/
hamiltoniancircuit_hamiltonianpath.rs
