problemreductions/rules/
highlyconnecteddeletion_ilp.rs

1//! Polynomial reduction from HighlyConnectedDeletion to binary ILP.
2//!
3//! One variable per unordered vertex pair records membership in the same cluster.
4//! Triangle inequalities make membership transitive. A binary flag per vertex
5//! distinguishes singleton clusters, and linear degree constraints enforce
6//! minimum degree strictly greater than half the cluster size otherwise.
7//!
8//! This degree condition is equivalent to high edge connectivity: for minimum
9//! degree d > k/2, a cut with smaller side a <= k/2 has at least
10//! a*(d-a+1) >= d edges. Conversely, edge connectivity never exceeds minimum
11//! degree. See <https://hueffner.de/falk/highly-connected-subgraph-sofsem15.pdf>.
12//!
13//! Maximize the number of non-loop edges kept inside clusters. Any feasible
14//! deletion can restore all internal edges without losing connectivity, so an
15//! optimal source solution is represented. Self-loops are always kept.
16
17use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
18use crate::models::graph::HighlyConnectedDeletion;
19use crate::reduction;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21use crate::topology::{Graph, SimpleGraph};
22
23/// Result of reducing HighlyConnectedDeletion to binary ILP.
24///
25/// Variables are unordered pairs in lexicographic order, followed by one
26/// non-singleton flag per vertex.
27#[derive(Debug, Clone)]
28pub struct ReductionHighlyConnectedDeletionToILP {
29    target: ILP<bool>,
30    /// Pair variable for each source edge; self-loops have no variable.
31    edge_variables: Vec<Option<usize>>,
32}
33
34impl ReductionResult for ReductionHighlyConnectedDeletionToILP {
35    type Source = HighlyConnectedDeletion<SimpleGraph>;
36    type Target = ILP<bool>;
37
38    fn target_problem(&self) -> &ILP<bool> {
39        &self.target
40    }
41
42    fn extract_solution(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_witness(
47            self.target_problem(),
48            target_solution,
49            |value| value.value.is_some(),
50            "target ILP assignment is infeasible",
51        )?;
52        Ok(self
53            .edge_variables
54            .iter()
55            .map(|variable| variable.is_some_and(|index| target_solution[index] == 0))
56            .collect())
57    }
58}
59
60// Three rows per vertex triple and two per vertex. Triple rows have three
61// nonzeros; each vertex row has at most n. All row magnitudes are <= max(n-1, 2).
62#[reduction(transform = {
63    exact {
64        num_vars = "num_vertices * (num_vertices + 1) / 2",
65    },
66    upper_bound {
67        num_constraints = "num_vertices^3 + 2 * num_vertices",
68        num_nonzeros = "3 * num_vertices^3 + 2 * num_vertices^2",
69        max_constraint_magnitude_bits = "num_vertices + 2",
70    },
71})]
72impl ReduceTo<ILP<bool>> for HighlyConnectedDeletion<SimpleGraph> {
73    type Result = ReductionHighlyConnectedDeletionToILP;
74
75    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
76        let graph = self.graph();
77        let n = graph.num_vertices();
78        let num_pairs = n.checked_mul(n.saturating_sub(1)).map(|value| value / 2);
79        let num_vars = num_pairs
80            .and_then(|pairs| pairs.checked_add(n))
81            .ok_or_else(|| {
82                crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(
83                    "counting pair and non-singleton variables",
84                )
85            })?;
86        let flag_offset = num_vars - n;
87        let max_companions =
88            Self::exact_i64(n.saturating_sub(1), "encoding the cluster-size bound")?;
89        // Lexicographic pair index: preceding row lengths, then the column offset.
90        // The checked n*(n-1) above also bounds these products for u < v < n.
91        let pair = |u: usize, v: usize| {
92            let (u, v) = (u.min(v), u.max(v));
93            u * n - u * (u + 1) / 2 + (v - u - 1)
94        };
95        let mut constraints = Vec::new();
96        for u in 0..n {
97            for v in u + 1..n {
98                for w in v + 1..n {
99                    let (a, b, c) = (pair(u, v), pair(u, w), pair(v, w));
100                    for (first, second, third) in [(a, b, c), (a, c, b), (b, c, a)] {
101                        constraints.push(LinearConstraint::le(
102                            vec![(first, 1), (second, 1), (third, -1)],
103                            1,
104                        ));
105                    }
106                }
107            }
108        }
109        for v in 0..n {
110            // s_v is the number of other vertices in v's cluster. The flag
111            // a_v is forced on for s_v > 0 by s_v <= (n-1)*a_v.
112            let mut size_terms = Vec::new();
113            let mut degree_terms = Vec::new();
114            for u in 0..n {
115                if u != v {
116                    let variable = pair(u, v);
117                    size_terms.push((variable, 1));
118                    // 2*d_v - s_v: count each distinct, non-loop neighbor once.
119                    degree_terms.push((variable, if graph.has_edge(u, v) { 1 } else { -1 }));
120                }
121            }
122            size_terms.push((flag_offset + v, -max_companions));
123            constraints.push(LinearConstraint::le(size_terms, 0));
124            // 2*d_v >= s_v + 2*a_v: singleton clusters pass, while other
125            // clusters require 2*d_v > s_v+1 and automatically exclude pairs.
126            degree_terms.push((flag_offset + v, -2));
127            constraints.push(LinearConstraint::ge(degree_terms, 0));
128        }
129        let edge_variables: Vec<_> = graph
130            .edges()
131            .iter()
132            .map(|&(u, v)| (u != v).then(|| pair(u, v)))
133            .collect();
134        // Duplicate edges contribute their multiplicity to the objective;
135        // self-loops are constant and need no objective term.
136        let objective = edge_variables
137            .iter()
138            .flatten()
139            .map(|&variable| (variable, 1))
140            .collect();
141        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
142            .map_err(Self::target_construction)?;
143        Ok(ReductionHighlyConnectedDeletionToILP {
144            target,
145            edge_variables,
146        })
147    }
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
152    vec![crate::example_db::specs::RuleExampleSpec {
153        id: "highlyconnecteddeletion_to_ilp",
154        build: || {
155            // Canonical example: triangle {0,1,2} + leaf vertex 3.
156            // Optimum deletes only the leaf edge (2,3); ILP keeps the triangle
157            // cluster and the {3} singleton.
158            let source = HighlyConnectedDeletion::new(SimpleGraph::new(
159                4,
160                vec![(0, 1), (0, 2), (1, 2), (2, 3)],
161            ));
162            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
163        },
164    }]
165}
166
167#[cfg(test)]
168#[path = "../unit_tests/rules/highlyconnecteddeletion_ilp.rs"]
169mod tests;
problemreductions/rules/highlyconnecteddeletion_ilp.rs

problemreductions/rules/
highlyconnecteddeletion_ilp.rs
