problemreductions/rules/highlyconnecteddeletion_ilp.rs
1//! Reduction from HighlyConnectedDeletion to ILP (Integer Linear Programming).
2//!
3//! Encodes the set-partitioning ILP of Hüffner, Komusiewicz, Liebtrau, and
4//! Niedermeier (IEEE/ACM TCBB 2014). Given a simple undirected graph
5//! `G = (V, E)`:
6//!
7//! - Enumerate the family `C(G)` of *feasible clusters*: every singleton plus
8//! every subset `S` with `|S| >= 3` whose induced subgraph `G[S]` is highly
9//! connected (edge connectivity strictly greater than `|S| / 2`).
10//! - Introduce a binary variable `x_S` per feasible cluster (1 iff `S` is one
11//! block of the chosen partition).
12//! - Partition constraints: for every vertex `v`,
13//! `sum_{S in C(G), v in S} x_S = 1`.
14//! - Maximize the number of kept (intra-cluster) edges:
15//! `max sum_{S in C(G)} |E(G[S])| * x_S`.
16//!
17//! Because `|E|` is fixed, maximizing kept internal edges minimizes deleted
18//! edges; the source value is recovered as
19//! `deleted_edges = |E| - ilp_objective`.
20//!
21//! Reference: Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, and Rolf
22//! Niedermeier, "Partitioning Biological Networks into Highly Connected
23//! Clusters with Maximum Edge Coverage," IEEE/ACM Transactions on
24//! Computational Biology and Bioinformatics 11(3):455–467, 2014.
25//! <https://doi.org/10.1109/TCBB.2013.177>
26
27use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
28use crate::models::graph::highly_connected_deletion::{induced_edge_count, is_feasible_cluster};
29use crate::models::graph::HighlyConnectedDeletion;
30use crate::reduction;
31use crate::rules::traits::{ReduceTo, ReductionResult};
32use crate::topology::{Graph, SimpleGraph};
33
34/// Result of reducing HighlyConnectedDeletion to ILP.
35///
36/// Variable layout (all binary):
37/// - `x_S` at index `c` is the indicator for the `c`-th feasible cluster
38/// stored in `clusters`. Indices follow the enumeration order produced by
39/// [`enumerate_feasible_clusters`], which always lists every singleton first
40/// followed by larger feasible clusters in subset-id order.
41#[derive(Debug, Clone)]
42pub struct ReductionHighlyConnectedDeletionToILP {
43 target: ILP<bool>,
44 /// Feasible clusters in variable order; `clusters[c]` is sorted ascending.
45 clusters: Vec<Vec<usize>>,
46 /// Source graph edges in the same order as `source.graph().edges()`.
47 edges: Vec<(usize, usize)>,
48}
49
50impl ReductionResult for ReductionHighlyConnectedDeletionToILP {
51 type Source = HighlyConnectedDeletion<SimpleGraph>;
52 type Target = ILP<bool>;
53
54 fn target_problem(&self) -> &ILP<bool> {
55 &self.target
56 }
57
58 /// Decode a binary ILP assignment into the source's edge-deletion config.
59 ///
60 /// For every source edge `(u, v)`, the edge is *kept* iff some chosen
61 /// cluster `S` (i.e. with `x_S = 1`) contains both `u` and `v`; otherwise
62 /// it is deleted (`config[e] = 1`).
63 fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
64 // Map every vertex to the (unique, for a feasible ILP solution) chosen
65 // cluster id. For partial/infeasible target assignments we fall back to
66 // `None`, which forces the corresponding source edges to be marked
67 // deleted -- preserving feasibility of `is_valid_solution` is the
68 // caller's responsibility, not ours.
69 let mut cluster_of: Vec<Option<usize>> = vec![None; vertex_count(&self.clusters)];
70 for (c, cluster) in self.clusters.iter().enumerate() {
71 if target_solution.get(c).copied().unwrap_or(0) == 1 {
72 for &v in cluster {
73 cluster_of[v] = Some(c);
74 }
75 }
76 }
77
78 self.edges
79 .iter()
80 .map(|&(u, v)| {
81 debug_assert!(
82 cluster_of[u].is_some() && cluster_of[v].is_some(),
83 "extract_solution invariant violated: edge ({}, {}) has endpoint(s) with no cluster assignment; a well-formed ILP witness assigns every vertex to exactly one selected cluster",
84 u,
85 v
86 );
87 match (cluster_of[u], cluster_of[v]) {
88 (Some(cu), Some(cv)) if cu == cv => 0,
89 _ => 1,
90 }
91 })
92 .collect()
93 }
94}
95
96/// Number of source vertices, recovered from the clusters list.
97///
98/// The reduction always enumerates the `n` singletons first, so any vertex id
99/// occurring anywhere in `clusters` is `< n`. We read `n` off the singletons
100/// for clarity and robustness.
101fn vertex_count(clusters: &[Vec<usize>]) -> usize {
102 clusters
103 .iter()
104 .filter(|c| c.len() == 1)
105 .map(|c| c[0] + 1)
106 .max()
107 .unwrap_or(0)
108}
109
110/// Enumerate every feasible cluster of `graph` in deterministic order.
111///
112/// Order: all `n` singletons first (subset ids `1, 2, 4, ...`), then larger
113/// feasible clusters listed by ascending bitmask of their vertex set. This
114/// gives a stable variable layout; tests pin the singleton prefix.
115fn enumerate_feasible_clusters(graph: &SimpleGraph) -> Vec<Vec<usize>> {
116 let n = graph.num_vertices();
117 debug_assert!(
118 n < 64,
119 "enumerate_feasible_clusters requires n < 64 due to u64 subset mask; got n={}",
120 n
121 );
122 let mut clusters: Vec<Vec<usize>> = Vec::new();
123
124 // Singletons first.
125 for v in 0..n {
126 clusters.push(vec![v]);
127 }
128
129 if n < 3 {
130 return clusters;
131 }
132
133 // Larger feasible clusters by ascending subset bitmask.
134 for mask in 1u64..(1u64 << n) {
135 let popcount = mask.count_ones() as usize;
136 if popcount < 3 {
137 continue;
138 }
139 let subset: Vec<usize> = (0..n).filter(|v| (mask >> v) & 1 == 1).collect();
140 if is_feasible_cluster(graph, &subset) {
141 clusters.push(subset);
142 }
143 }
144
145 clusters
146}
147
148#[reduction(
149 overhead = {
150 num_vars = "2^num_vertices",
151 num_constraints = "num_vertices",
152 }
153)]
154impl ReduceTo<ILP<bool>> for HighlyConnectedDeletion<SimpleGraph> {
155 type Result = ReductionHighlyConnectedDeletionToILP;
156
157 fn reduce_to(&self) -> Self::Result {
158 let graph = self.graph();
159 let n = graph.num_vertices();
160 let clusters = enumerate_feasible_clusters(graph);
161 let num_vars = clusters.len();
162
163 // Partition constraints: for every vertex v, sum_{S : v in S} x_S = 1.
164 // Each constraint is built by scanning the cluster list once per
165 // vertex; total work is O(n * sum |S|) which stays tractable for the
166 // small graphs we use in tests.
167 let mut constraints: Vec<LinearConstraint> = Vec::with_capacity(n);
168 for v in 0..n {
169 let terms: Vec<(usize, f64)> = clusters
170 .iter()
171 .enumerate()
172 .filter_map(|(c, cluster)| {
173 if cluster.binary_search(&v).is_ok() {
174 Some((c, 1.0))
175 } else {
176 None
177 }
178 })
179 .collect();
180 constraints.push(LinearConstraint::eq(terms, 1.0));
181 }
182
183 // Objective: maximize sum_S |E(G[S])| * x_S.
184 let objective: Vec<(usize, f64)> = clusters
185 .iter()
186 .enumerate()
187 .map(|(c, cluster)| (c, induced_edge_count(graph, cluster) as f64))
188 .collect();
189
190 let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
191
192 ReductionHighlyConnectedDeletionToILP {
193 target,
194 clusters,
195 edges: graph.edges(),
196 }
197 }
198}
199
200#[cfg(feature = "example-db")]
201pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
202 vec![crate::example_db::specs::RuleExampleSpec {
203 id: "highlyconnecteddeletion_to_ilp",
204 build: || {
205 // Canonical issue #1023 instance: triangle {0,1,2} + leaf vertex 3.
206 // Optimum deletes only the leaf edge (2,3); ILP keeps the triangle
207 // cluster and the {3} singleton.
208 let source = HighlyConnectedDeletion::new(SimpleGraph::new(
209 4,
210 vec![(0, 1), (0, 2), (1, 2), (2, 3)],
211 ));
212 crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
213 },
214 }]
215}
216
217#[cfg(test)]
218#[path = "../unit_tests/rules/highlyconnecteddeletion_ilp.rs"]
219mod tests;