problemreductions/rules/
hamiltoniancircuit_biconnectivityaugmentation.rs

1//! Reduction from HamiltonianCircuit to BiconnectivityAugmentation.
2//!
3//! Based on the Eswaran & Tarjan (1976) approach:
4//!
5//! For n < 3, the source has no circuit: output three isolated vertices with
6//! no candidate edges and budget zero, a fixed infeasible target.
7//!
8//! Given a Hamiltonian Circuit instance G = (V, E) with n >= 3 vertices, construct a
9//! BiconnectivityAugmentation instance as follows:
10//!
11//! 1. Start with an edgeless graph on n vertices.
12//! 2. For each pair (u, v) with u < v, create a potential edge with:
13//!    - weight 1 if {u, v} is in E
14//!    - weight 2 if {u, v} is not in E
15//! 3. Set budget B = n.
16//!
17//! G has a Hamiltonian circuit iff there exists a biconnectivity augmentation of
18//! cost exactly n using only weight-1 edges (i.e., original edges).
19//!
20//! The selected weight-1 edges form a Hamiltonian cycle in G, which is necessarily
21//! biconnected. Any augmentation using a weight-2 edge would cost at least n+1,
22//! exceeding the budget of n (since at least n edges are needed for biconnectivity).
23
24use crate::models::graph::{BiconnectivityAugmentation, HamiltonianCircuit};
25use crate::reduction;
26use crate::rules::traits::{ReduceTo, ReductionResult};
27use crate::topology::{Graph, SimpleGraph};
28
29/// Result of reducing HamiltonianCircuit to BiconnectivityAugmentation.
30///
31/// Stores the target problem and the mapping from potential edge indices to
32/// vertex pairs for solution extraction.
33#[derive(Debug, Clone)]
34pub struct ReductionHamiltonianCircuitToBiconnectivityAugmentation {
35    target: BiconnectivityAugmentation<SimpleGraph, i64>,
36    /// Number of vertices in the original graph.
37    num_vertices: usize,
38    /// Potential edges as (u, v) pairs, in the same order as the target's potential_weights.
39    potential_edges: Vec<(usize, usize)>,
40}
41
42impl ReductionResult for ReductionHamiltonianCircuitToBiconnectivityAugmentation {
43    type Source = HamiltonianCircuit<SimpleGraph>;
44    type Target = BiconnectivityAugmentation<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 augmentation is infeasible",
59        )?;
60
61        Ok({
62            let n = self.num_vertices;
63            if n < 3 {
64                return Err(crate::rules::ExtractionError::invalid(
65                    "a Hamiltonian circuit requires at least three vertices",
66                ));
67            }
68
69            // Collect selected edges (those with config value 1)
70            let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
71            for (i, &(u, v)) in self.potential_edges.iter().enumerate() {
72                if target_solution[i] {
73                    adj[u].push(v);
74                    adj[v].push(u);
75                }
76            }
77
78            // Check that every vertex has exactly degree 2 (Hamiltonian cycle)
79            if adj.iter().any(|neighbors| neighbors.len() != 2) {
80                return Err(crate::rules::ExtractionError::invalid(
81                    "selected edges do not give every source vertex degree two",
82                ));
83            }
84
85            // Walk the cycle starting from vertex 0
86            let mut circuit = Vec::with_capacity(n);
87            circuit.push(0);
88            let mut prev = 0;
89            let mut current = adj[0][0];
90            while current != 0 {
91                circuit.push(current);
92                let next = if adj[current][0] == prev {
93                    adj[current][1]
94                } else {
95                    adj[current][0]
96                };
97                prev = current;
98                current = next;
99
100                // Safety: if we've visited more than n vertices, something is wrong
101                if circuit.len() > n {
102                    return Err(crate::rules::ExtractionError::invalid(
103                        "selected edges revisit a source vertex",
104                    ));
105                }
106            }
107
108            if circuit.len() == n {
109                circuit
110            } else {
111                return Err(crate::rules::ExtractionError::invalid(
112                    "selected edges do not form a spanning circuit",
113                ));
114            }
115        })
116    }
117}
118
119#[crate::aggregate_reduction(identity)]
120impl crate::rules::AggregateReductionResult
121    for ReductionHamiltonianCircuitToBiconnectivityAugmentation
122{
123}
124
125#[reduction(
126    transform = upper_bound {
127        max_numeric_magnitude_bits = "num_vertices + 1",
128        num_vertices = "num_vertices + 3",
129        num_edges = "0",
130        num_potential_edges = "num_vertices * (num_vertices - 1) / 2",
131    }
132)]
133impl ReduceTo<BiconnectivityAugmentation<SimpleGraph, i64>> for HamiltonianCircuit<SimpleGraph> {
134    type Result = ReductionHamiltonianCircuitToBiconnectivityAugmentation;
135
136    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
137        let n = self.num_vertices();
138        if n < 3 {
139            return Ok(ReductionHamiltonianCircuitToBiconnectivityAugmentation {
140                target: BiconnectivityAugmentation::new(SimpleGraph::empty(3), vec![], 0),
141                num_vertices: n,
142                potential_edges: vec![],
143            });
144        }
145        let graph = self.graph();
146
147        // Edgeless initial graph
148        let initial_graph = SimpleGraph::empty(n);
149
150        // Create potential edges for all pairs (u, v) with u < v
151        let mut potential_weights = Vec::new();
152        let mut potential_edges = Vec::new();
153        for u in 0..n {
154            for v in (u + 1)..n {
155                let weight = if graph.has_edge(u, v) { 1 } else { 2 };
156                potential_weights.push((u, v, weight));
157                potential_edges.push((u, v));
158            }
159        }
160
161        // Budget = n (exactly enough for n weight-1 edges)
162        let budget = i64::try_from(n).map_err(|_| {
163            crate::rules::ReductionError::integer_overflow::<
164                HamiltonianCircuit<SimpleGraph>,
165                BiconnectivityAugmentation<SimpleGraph, i64>,
166            >("converting the vertex count to the target budget")
167        })?;
168
169        let target = BiconnectivityAugmentation::new(initial_graph, potential_weights, budget);
170
171        Ok(ReductionHamiltonianCircuitToBiconnectivityAugmentation {
172            target,
173            num_vertices: n,
174            potential_edges,
175        })
176    }
177}
178
179#[cfg(feature = "example-db")]
180pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
181    use crate::export::SolutionPair;
182
183    vec![crate::example_db::specs::RuleExampleSpec {
184        id: "hamiltoniancircuit_to_biconnectivityaugmentation",
185        build: || {
186            // Square graph (4-cycle): 0-1-2-3-0
187            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
188            // Potential edges for 4 vertices (indices 0..5):
189            // 0: (0,1) w=1, 1: (0,2) w=2, 2: (0,3) w=1,
190            // 3: (1,2) w=1, 4: (1,3) w=2, 5: (2,3) w=1
191            // HC 0-1-2-3-0 selects edges (0,1),(1,2),(2,3),(0,3) => indices 0,3,5,2
192            // Config: [1, 0, 1, 1, 0, 1]
193            crate::example_db::specs::rule_example_with_witness::<
194                _,
195                BiconnectivityAugmentation<SimpleGraph, i64>,
196            >(
197                source,
198                SolutionPair {
199                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
200                    target_config: serde_json::json!(vec![true, false, true, true, false, true]),
201                },
202            )
203        },
204    }]
205}
206
207#[cfg(test)]
208#[path = "../unit_tests/rules/hamiltoniancircuit_biconnectivityaugmentation.rs"]
209mod tests;
problemreductions/rules/hamiltoniancircuit_biconnectivityaugmentation.rs

problemreductions/rules/
hamiltoniancircuit_biconnectivityaugmentation.rs
