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(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_witness(
44            self.target_problem(),
45            target_solution,
46            |value| value.0,
47            "target witness is not satisfying",
48        )?;
49
50        Ok({
51            let n = self.num_original_vertices;
52            if n == 0 {
53                return Ok(vec![]);
54            }
55
56            let v_prime = n; // index of duplicated vertex v'
57            let s = n + 1; // pendant attached to v=0
58            let t = n + 2; // pendant attached to v'
59
60            // The two pendants force any valid witness to have endpoints s and t.
61            let reversed;
62            let oriented = match (target_solution.first(), target_solution.last()) {
63                (Some(&start), Some(&end)) if start == s && end == t => target_solution,
64                (Some(&start), Some(&end)) if start == t && end == s => {
65                    reversed = target_solution.iter().copied().rev().collect::<Vec<_>>();
66                    reversed.as_slice()
67                }
68                _ => {
69                    return Err(crate::rules::ExtractionError::invalid(
70                        "target path does not have the required pendant endpoints",
71                    ))
72                }
73            };
74
75            if oriented.get(1) != Some(&0) || oriented.get(n + 1) != Some(&v_prime) {
76                return Err(crate::rules::ExtractionError::invalid(
77                    "target path does not traverse the duplicated source vertex correctly",
78                ));
79            }
80
81            oriented[1..=n].to_vec()
82        })
83    }
84}
85
86#[crate::aggregate_reduction(identity)]
87impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToHamiltonianPath {}
88
89// Both branches allocate n+3 vertices. The main branch copies m edges,
90// at most m neighbor occurrences of vertex 0, and two pendant edges.
91#[reduction(transform = {
92    exact {
93        num_vertices = "num_vertices + 3",
94    },
95    upper_bound {
96        num_edges = "2 * num_edges + 2",
97    },
98})]
99impl ReduceTo<HamiltonianPath<SimpleGraph>> for HamiltonianCircuit<SimpleGraph> {
100    type Result = ReductionHamiltonianCircuitToHamiltonianPath;
101
102    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
103        let n = self.num_vertices();
104
105        // HC is unsatisfiable for n < 3; return a trivially unsatisfiable HP instance.
106        if n < 3 {
107            let target_graph = SimpleGraph::empty(n + 3);
108            let target = HamiltonianPath::new(target_graph);
109            return Ok(ReductionHamiltonianCircuitToHamiltonianPath {
110                target,
111                num_original_vertices: n,
112            });
113        }
114
115        let source_graph = self.graph();
116
117        // New vertex indices:
118        // 0..n-1: original vertices
119        // n: v' (duplicate of vertex 0)
120        // n+1: s (pendant of vertex 0)
121        // n+2: t (pendant of v')
122        let v_prime = n;
123        let s = n + 1;
124        let t = n + 2;
125
126        let mut edges: Vec<(usize, usize)> = Vec::new();
127
128        // 1. Copy all original edges
129        for (u, v) in source_graph.edges() {
130            edges.push((u, v));
131        }
132
133        // 2. Connect v' to all neighbors of vertex 0
134        for neighbor in source_graph.neighbors(0) {
135            edges.push((v_prime, neighbor));
136        }
137
138        // 3. Add pendant edge {s, 0}
139        edges.push((s, 0));
140
141        // 4. Add pendant edge {t, v'}
142        edges.push((t, v_prime));
143
144        let target_graph = SimpleGraph::new(n + 3, edges);
145        let target = HamiltonianPath::new(target_graph);
146
147        Ok(ReductionHamiltonianCircuitToHamiltonianPath {
148            target,
149            num_original_vertices: n,
150        })
151    }
152}
153
154#[cfg(feature = "example-db")]
155pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
156    use crate::export::SolutionPair;
157
158    vec![crate::example_db::specs::RuleExampleSpec {
159        id: "hamiltoniancircuit_to_hamiltonianpath",
160        build: || {
161            // Square graph (4-cycle): 0-1-2-3-0
162            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
163            crate::example_db::specs::rule_example_with_witness::<_, HamiltonianPath<SimpleGraph>>(
164                source,
165                SolutionPair {
166                    // HC solution: visit vertices in order 0, 1, 2, 3
167                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
168                    // HP solution on G' (7 vertices): s=5, 0, 1, 2, 3, v'=4, t=6
169                    target_config: serde_json::json!(vec![5, 0, 1, 2, 3, 4, 6]),
170                },
171            )
172        },
173    }]
174}
175
176#[cfg(test)]
177#[path = "../unit_tests/rules/hamiltoniancircuit_hamiltonianpath.rs"]
178mod tests;
problemreductions/rules/hamiltoniancircuit_hamiltonianpath.rs

problemreductions/rules/
hamiltoniancircuit_hamiltonianpath.rs
