problemreductions/rules/
hamiltoniancircuit_ruralpostman.rs

1//! Reduction from HamiltonianCircuit to RuralPostman.
2//!
3//! Vertex-splitting construction inspired by Lenstra & Rinnooy Kan (1976).
4//!
5//! # Construction
6//!
7//! Given a graph G = (V, E) with n vertices and m edges:
8//! - Split each vertex v_i into v_i^a (vertex 2i) and v_i^b (vertex 2i+1).
9//! - Add a required edge {v_i^a, v_i^b} with weight 1 for each vertex (n required edges).
10//! - For each edge {v_i, v_j} in E, add two non-required connectivity edges:
11//!   {v_i^b, v_j^a} and {v_j^b, v_i^a}, each with weight 1.
12//!
13//! The target graph has 2n vertices, n + 2m edges, and n required edges.
14//!
15//! # Correctness
16//!
17//! G has a Hamiltonian circuit iff the optimal RPP cost equals 2n:
18//! - If G has HC (v_{p_0}, ..., v_{p_{n-1}}): the RPP tour traverses
19//!   v_{p_0}^a -> v_{p_0}^b -> v_{p_1}^a -> v_{p_1}^b -> ... -> v_{p_0}^a,
20//!   using n required edges (cost n) and n connectivity edges (cost n), total 2n.
21//! - If G has no HC: every valid RPP tour covering all required edges needs
22//!   strictly more than n connectivity edges (the bipartite graph between
23//!   b-vertices and a-vertices does not admit a perfect matching corresponding
24//!   to a Hamiltonian circuit), so cost > 2n.
25
26use crate::models::decision::Decision;
27use crate::models::graph::{HamiltonianCircuit, RuralPostman};
28use crate::reduction;
29use crate::rules::traits::{ReduceTo, ReductionResult};
30use crate::topology::{Graph, SimpleGraph};
31
32/// Result of reducing HamiltonianCircuit to RuralPostman.
33#[derive(Debug, Clone)]
34pub struct ReductionHamiltonianCircuitToRuralPostman {
35    target: Decision<RuralPostman<SimpleGraph, i64>>,
36    /// Number of vertices in the original graph.
37    n: usize,
38    /// Edges of the original graph (for solution extraction).
39    source_edges: Vec<(usize, usize)>,
40}
41
42impl ReductionResult for ReductionHamiltonianCircuitToRuralPostman {
43    type Source = HamiltonianCircuit<SimpleGraph>;
44    type Target = Decision<RuralPostman<SimpleGraph, i64>>;
45
46    fn target_problem(&self) -> &Self::Target {
47        &self.target
48    }
49
50    fn extract_solution(
51        &self,
52        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
53    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
54        crate::rules::traits::validate_target_witness(
55            self.target_problem(),
56            target_solution,
57            |value| value.0,
58            "target witness does not certify a YES answer for the source",
59        )?;
60
61        Ok({
62            // The target solution is edge multiplicities.
63            // Required edges are indices 0..n (the {v_i^a, v_i^b} edges).
64            // Connectivity edges start at index n.
65            // For each source edge (v_i, v_j) at source index k:
66            //   target edge n + 2*k is {v_i^b, v_j^a}
67            //   target edge n + 2*k + 1 is {v_j^b, v_i^a}
68            //
69            // A connectivity edge {v_i^b, v_j^a} used with multiplicity 1 means
70            // the tour goes from vertex i to vertex j (j follows i in the HC).
71
72            let n = self.n;
73
74            // Build successor map from connectivity edges used exactly once
75            let mut successor = vec![usize::MAX; n];
76            for (k, &(vi, vj)) in self.source_edges.iter().enumerate() {
77                let fwd_idx = n + 2 * k; // {v_i^b, v_j^a}
78                let bwd_idx = n + 2 * k + 1; // {v_j^b, v_i^a}
79
80                let fwd_mult = target_solution[fwd_idx];
81                let bwd_mult = target_solution[bwd_idx];
82
83                // In an optimal HC solution, each connectivity edge is used 0 or 1 times.
84                // Each vertex should have exactly one outgoing connectivity edge.
85                if fwd_mult > 0 && successor[vi] == usize::MAX {
86                    successor[vi] = vj;
87                }
88                if bwd_mult > 0 && successor[vj] == usize::MAX {
89                    successor[vj] = vi;
90                }
91            }
92
93            // Walk the successor chain starting from vertex 0
94            let mut cycle = Vec::with_capacity(n);
95            let mut current = 0;
96            for _ in 0..n {
97                cycle.push(current);
98                let next = successor[current];
99                if next == usize::MAX {
100                    return Err(crate::rules::ExtractionError::invalid(
101                        "target tour does not provide one successor for every source vertex",
102                    ));
103                }
104                current = next;
105            }
106
107            cycle
108        })
109    }
110}
111
112#[crate::aggregate_reduction(identity)]
113impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToRuralPostman {}
114
115#[reduction(
116    transform = exact {
117        num_vertices = "2 * num_vertices",
118        num_edges = "num_vertices + 2 * num_edges",
119        num_required_edges = "num_vertices",
120    }
121)]
122impl ReduceTo<Decision<RuralPostman<SimpleGraph, i64>>> for HamiltonianCircuit<SimpleGraph> {
123    type Result = ReductionHamiltonianCircuitToRuralPostman;
124
125    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
126        let n = self.num_vertices();
127        let source_edges: Vec<(usize, usize)> = self.graph().edges();
128        let m = source_edges.len();
129
130        // Build target graph with 2n vertices
131        let num_target_edges = n + 2 * m;
132        let mut target_edges = Vec::with_capacity(num_target_edges);
133        let mut edge_weights = Vec::with_capacity(num_target_edges);
134        let mut required_edges = Vec::with_capacity(n);
135
136        // Required edges: {v_i^a, v_i^b} = {2i, 2i+1} with weight 1
137        for i in 0..n {
138            target_edges.push((2 * i, 2 * i + 1));
139            edge_weights.push(1);
140            required_edges.push(i); // edge index i is required
141        }
142
143        // Connectivity edges for each source edge {v_i, v_j}:
144        //   {v_i^b, v_j^a} = {2i+1, 2j} with weight 1
145        //   {v_j^b, v_i^a} = {2j+1, 2i} with weight 1
146        for &(vi, vj) in &source_edges {
147            target_edges.push((2 * vi + 1, 2 * vj));
148            edge_weights.push(1);
149            target_edges.push((2 * vj + 1, 2 * vi));
150            edge_weights.push(1);
151        }
152
153        let target_graph = SimpleGraph::new(2 * n, target_edges);
154        let target = RuralPostman::new(target_graph, edge_weights, required_edges);
155
156        Ok(ReductionHamiltonianCircuitToRuralPostman {
157            target: Decision::new(
158                target,
159                if n < 3 {
160                    -1
161                } else {
162                    <Self as ReduceTo<Decision<RuralPostman<SimpleGraph, i64>>>>::exact_i64(
163                        2 * n,
164                        "encoding the route bound",
165                    )?
166                },
167            ),
168            n,
169            source_edges,
170        })
171    }
172}
173
174#[cfg(feature = "example-db")]
175pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
176    use crate::export::SolutionPair;
177
178    vec![crate::example_db::specs::RuleExampleSpec {
179        id: "hamiltoniancircuit_to_ruralpostman",
180        build: || {
181            // Triangle graph: 3 vertices, 3 edges, HC = [0, 1, 2]
182            let source = HamiltonianCircuit::new(SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]));
183
184            // Target graph has 6 vertices, 3 + 6 = 9 edges, 3 required edges.
185            // HC [0, 1, 2] uses connectivity edges:
186            //   0->1: fwd edge of source edge 0=(0,1), idx=3
187            //   1->2: fwd edge of source edge 1=(1,2), idx=5
188            //   2->0: bwd edge of source edge 2=(0,2), idx=8
189            // Required edges all have multiplicity 1.
190            // target_config = [1, 1, 1, 1, 0, 1, 0, 0, 1]
191            crate::example_db::specs::rule_example_with_witness::<
192                _,
193                Decision<RuralPostman<SimpleGraph, i64>>,
194            >(
195                source,
196                SolutionPair {
197                    source_config: serde_json::json!(vec![0, 1, 2]),
198                    target_config: serde_json::json!(vec![1, 1, 1, 1, 0, 1, 0, 0, 1]),
199                },
200            )
201        },
202    }]
203}
204
205#[cfg(test)]
206#[path = "../unit_tests/rules/hamiltoniancircuit_ruralpostman.rs"]
207mod tests;
problemreductions/rules/hamiltoniancircuit_ruralpostman.rs

problemreductions/rules/
hamiltoniancircuit_ruralpostman.rs
