problemreductions/rules/
maximumindependentset_integralflowbundles.rs

1//! Reduction from MaximumIndependentSet to IntegralFlowBundles (Sahni 1974).
2//!
3//! For a graph G = (V, E) with n = |V| vertices and m = |E| edges:
4//!
5//! 1. Create a directed graph with n + 2 vertices: source s, intermediate
6//!    vertices w_0, ..., w_{n-1}, and sink t.
7//! 2. For each vertex v_i, create two arcs: arc_in_i = (s, w_i) and
8//!    arc_out_i = (w_i, t). Arc indices: arc_in_i = 2i, arc_out_i = 2i + 1.
9//! 3. For each edge {v_i, v_j}, create bundle {arc_out_i, arc_out_j} with
10//!    capacity 1 (conflict constraint: at most one endpoint selected).
11//! 4. For each vertex v_i, create bundle {arc_in_i, arc_out_i} with capacity 2.
12//!    Flow conservation at w_i forces arc_in_i = arc_out_i = f_i, so the
13//!    bundle sum is 2*f_i <= 2, giving f_i in {0, 1}. This bundle also
14//!    ensures every arc is covered by at least one bundle.
15//! 5. Set requirement R = 1 (any non-empty independent set gives a feasible flow).
16//!
17//! An independent set of size k corresponds to a feasible flow of value k.
18//! The bundle constraints ensure only independent sets produce valid flows.
19
20use crate::models::graph::{IntegralFlowBundles, MaximumIndependentSet};
21use crate::reduction;
22use crate::rules::traits::{ReduceTo, ReductionResult};
23use crate::topology::{Graph, SimpleGraph};
24
25#[cfg(feature = "example-db")]
26use crate::solvers::BruteForce;
27
28/// Result of reducing MaximumIndependentSet to IntegralFlowBundles.
29#[derive(Debug, Clone)]
30pub struct ReductionMISToIFB {
31    target: IntegralFlowBundles,
32    /// Number of vertices in the source graph.
33    num_source_vertices: usize,
34}
35
36impl ReductionResult for ReductionMISToIFB {
37    type Source = MaximumIndependentSet<SimpleGraph, i32>;
38    type Target = IntegralFlowBundles;
39
40    fn target_problem(&self) -> &Self::Target {
41        &self.target
42    }
43
44    /// Extract solution: vertex i is selected iff arc_out_i (index 2i + 1)
45    /// has nonzero flow.
46    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
47        (0..self.num_source_vertices)
48            .map(|i| {
49                if target_solution.get(2 * i + 1).copied().unwrap_or(0) > 0 {
50                    1
51                } else {
52                    0
53                }
54            })
55            .collect()
56    }
57}
58
59#[reduction(
60    overhead = {
61        num_vertices = "num_vertices + 2",
62        num_arcs = "2 * num_vertices",
63        num_bundles = "num_edges + num_vertices",
64    }
65)]
66impl ReduceTo<IntegralFlowBundles> for MaximumIndependentSet<SimpleGraph, i32> {
67    type Result = ReductionMISToIFB;
68
69    fn reduce_to(&self) -> Self::Result {
70        let n = self.graph().num_vertices();
71        let edges = self.graph().edges();
72
73        // Set requirement = 1: any independent set of size >= 1 maps to a feasible flow.
74        // The bundle constraints ensure only independent sets produce valid flows.
75        let requirement = 1u64;
76
77        // Vertices: s = 0, w_i = i + 1 (for i in 0..n), t = n + 1
78        let source_vertex = 0;
79        let sink_vertex = n + 1;
80
81        // Arcs: arc_in_i = (s, w_i), arc_out_i = (w_i, t)
82        let mut arcs = Vec::with_capacity(2 * n);
83        for i in 0..n {
84            arcs.push((source_vertex, i + 1)); // arc_in_i at index 2*i
85            arcs.push((i + 1, sink_vertex)); // arc_out_i at index 2*i + 1
86        }
87
88        let directed_graph = crate::topology::DirectedGraph::new(n + 2, arcs);
89
90        // Bundles: edge bundles + vertex bundles
91        let mut bundles = Vec::with_capacity(edges.len() + n);
92        let mut bundle_capacities = Vec::with_capacity(edges.len() + n);
93
94        // Edge bundles: for each edge {v_i, v_j}, bundle {arc_out_i, arc_out_j} with cap 1
95        for &(u, v) in &edges {
96            bundles.push(vec![2 * u + 1, 2 * v + 1]);
97            bundle_capacities.push(1);
98        }
99
100        // Vertex bundles: for each vertex v_i, bundle {arc_in_i, arc_out_i} with cap 2.
101        // Flow conservation forces arc_in_i = arc_out_i = f_i, so bundle sum =
102        // 2*f_i <= 2, hence f_i in {0, 1}. This also ensures every arc is in
103        // at least one bundle (required by IntegralFlowBundles).
104        for i in 0..n {
105            bundles.push(vec![2 * i, 2 * i + 1]);
106            bundle_capacities.push(2);
107        }
108
109        let target = IntegralFlowBundles::new(
110            directed_graph,
111            source_vertex,
112            sink_vertex,
113            bundles,
114            bundle_capacities,
115            requirement,
116        );
117
118        ReductionMISToIFB {
119            target,
120            num_source_vertices: n,
121        }
122    }
123}
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    use crate::export::SolutionPair;
128
129    vec![crate::example_db::specs::RuleExampleSpec {
130        id: "maximumindependentset_to_integralflowbundles",
131        build: || {
132            // Path graph: 0-1-2-3, unit weights
133            // Optimal MIS = {0, 2} or {1, 3} or {0, 3}, size = 2
134            let source = MaximumIndependentSet::new(
135                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
136                vec![1i32; 4],
137            );
138            let reduction = ReduceTo::<IntegralFlowBundles>::reduce_to(&source);
139            let target = reduction.target_problem();
140
141            let target_witness = BruteForce::new()
142                .find_witness(target)
143                .expect("target should have a feasible solution");
144            let source_witness = reduction.extract_solution(&target_witness);
145
146            crate::example_db::specs::rule_example_with_witness::<_, IntegralFlowBundles>(
147                source,
148                SolutionPair {
149                    source_config: source_witness,
150                    target_config: target_witness,
151                },
152            )
153        },
154    }]
155}
156
157#[cfg(test)]
158#[path = "../unit_tests/rules/maximumindependentset_integralflowbundles.rs"]
159mod tests;
problemreductions/rules/maximumindependentset_integralflowbundles.rs

problemreductions/rules/
maximumindependentset_integralflowbundles.rs
