problemreductions/rules/
hamiltoniancircuit_biconnectivityaugmentation.rs

1//! Reduction from HamiltonianCircuit to BiconnectivityAugmentation.
2//!
3//! Based on the Eswaran & Tarjan (1976) approach:
4//!
5//! Given a Hamiltonian Circuit instance G = (V, E) with n vertices, construct a
6//! BiconnectivityAugmentation instance as follows:
7//!
8//! 1. Start with an edgeless graph on n vertices.
9//! 2. For each pair (u, v) with u < v, create a potential edge with:
10//!    - weight 1 if {u, v} is in E
11//!    - weight 2 if {u, v} is not in E
12//! 3. Set budget B = n.
13//!
14//! G has a Hamiltonian circuit iff there exists a biconnectivity augmentation of
15//! cost exactly n using only weight-1 edges (i.e., original edges).
16//!
17//! The selected weight-1 edges form a Hamiltonian cycle in G, which is necessarily
18//! biconnected. Any augmentation using a weight-2 edge would cost at least n+1,
19//! exceeding the budget of n (since at least n edges are needed for biconnectivity).
20
21use crate::models::graph::{BiconnectivityAugmentation, HamiltonianCircuit};
22use crate::reduction;
23use crate::rules::traits::{ReduceTo, ReductionResult};
24use crate::topology::{Graph, SimpleGraph};
25
26/// Result of reducing HamiltonianCircuit to BiconnectivityAugmentation.
27///
28/// Stores the target problem and the mapping from potential edge indices to
29/// vertex pairs for solution extraction.
30#[derive(Debug, Clone)]
31pub struct ReductionHamiltonianCircuitToBiconnectivityAugmentation {
32    target: BiconnectivityAugmentation<SimpleGraph, i32>,
33    /// Number of vertices in the original graph.
34    num_vertices: usize,
35    /// Potential edges as (u, v) pairs, in the same order as the target's potential_weights.
36    potential_edges: Vec<(usize, usize)>,
37}
38
39impl ReductionResult for ReductionHamiltonianCircuitToBiconnectivityAugmentation {
40    type Source = HamiltonianCircuit<SimpleGraph>;
41    type Target = BiconnectivityAugmentation<SimpleGraph, i32>;
42
43    fn target_problem(&self) -> &Self::Target {
44        &self.target
45    }
46
47    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
48        let n = self.num_vertices;
49        if n < 3 {
50            return vec![0; n];
51        }
52
53        // Collect selected edges (those with config value 1)
54        let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
55        for (i, &(u, v)) in self.potential_edges.iter().enumerate() {
56            if i < target_solution.len() && target_solution[i] == 1 {
57                adj[u].push(v);
58                adj[v].push(u);
59            }
60        }
61
62        // Check that every vertex has exactly degree 2 (Hamiltonian cycle)
63        if adj.iter().any(|neighbors| neighbors.len() != 2) {
64            return vec![0; n];
65        }
66
67        // Walk the cycle starting from vertex 0
68        let mut circuit = Vec::with_capacity(n);
69        circuit.push(0);
70        let mut prev = 0;
71        let mut current = adj[0][0];
72        while current != 0 {
73            circuit.push(current);
74            let next = if adj[current][0] == prev {
75                adj[current][1]
76            } else {
77                adj[current][0]
78            };
79            prev = current;
80            current = next;
81
82            // Safety: if we've visited more than n vertices, something is wrong
83            if circuit.len() > n {
84                return vec![0; n];
85            }
86        }
87
88        if circuit.len() == n {
89            circuit
90        } else {
91            vec![0; n]
92        }
93    }
94}
95
96#[reduction(
97    overhead = {
98        num_vertices = "num_vertices",
99        num_edges = "0",
100        num_potential_edges = "num_vertices * (num_vertices - 1) / 2",
101    }
102)]
103impl ReduceTo<BiconnectivityAugmentation<SimpleGraph, i32>> for HamiltonianCircuit<SimpleGraph> {
104    type Result = ReductionHamiltonianCircuitToBiconnectivityAugmentation;
105
106    fn reduce_to(&self) -> Self::Result {
107        let n = self.num_vertices();
108        let graph = self.graph();
109
110        // Edgeless initial graph
111        let initial_graph = SimpleGraph::empty(n);
112
113        // Create potential edges for all pairs (u, v) with u < v
114        let mut potential_weights = Vec::new();
115        let mut potential_edges = Vec::new();
116        for u in 0..n {
117            for v in (u + 1)..n {
118                let weight = if graph.has_edge(u, v) { 1 } else { 2 };
119                potential_weights.push((u, v, weight));
120                potential_edges.push((u, v));
121            }
122        }
123
124        // Budget = n (exactly enough for n weight-1 edges)
125        let budget = n as i32;
126
127        let target = BiconnectivityAugmentation::new(initial_graph, potential_weights, budget);
128
129        ReductionHamiltonianCircuitToBiconnectivityAugmentation {
130            target,
131            num_vertices: n,
132            potential_edges,
133        }
134    }
135}
136
137#[cfg(feature = "example-db")]
138pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
139    use crate::export::SolutionPair;
140
141    vec![crate::example_db::specs::RuleExampleSpec {
142        id: "hamiltoniancircuit_to_biconnectivityaugmentation",
143        build: || {
144            // Square graph (4-cycle): 0-1-2-3-0
145            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
146            // Potential edges for 4 vertices (indices 0..5):
147            // 0: (0,1) w=1, 1: (0,2) w=2, 2: (0,3) w=1,
148            // 3: (1,2) w=1, 4: (1,3) w=2, 5: (2,3) w=1
149            // HC 0-1-2-3-0 selects edges (0,1),(1,2),(2,3),(0,3) => indices 0,3,5,2
150            // Config: [1, 0, 1, 1, 0, 1]
151            crate::example_db::specs::rule_example_with_witness::<
152                _,
153                BiconnectivityAugmentation<SimpleGraph, i32>,
154            >(
155                source,
156                SolutionPair {
157                    source_config: vec![0, 1, 2, 3],
158                    target_config: vec![1, 0, 1, 1, 0, 1],
159                },
160            )
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/hamiltoniancircuit_biconnectivityaugmentation.rs"]
167mod tests;
problemreductions/rules/hamiltoniancircuit_biconnectivityaugmentation.rs

problemreductions/rules/
hamiltoniancircuit_biconnectivityaugmentation.rs
