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

problemreductions/rules/
hamiltoniancircuit_hamiltonianpath.rs
