problemreductions/rules/
decisionmaximumindependentset_integralflowbundles.rs

1//! Unit-weight decision independent set to integral flow with bundles.
2//!
3//! Sahni (1974), Theorem 2.2(b)(iv), uses a cardinality threshold and repeated
4//! flow queries to recover an optimum. This direct rule preserves one decision
5//! query. An auxiliary binary path shifts the threshold to remain positive,
6//! including empty graphs and nonpositive source bounds.
7
8use crate::models::decision::Decision;
9use crate::models::graph::{IntegralFlowBundles, MaximumIndependentSet};
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13use crate::types::One;
14
15/// Result of a unit-weight independent-set decision reduction.
16#[derive(Debug, Clone)]
17pub struct ReductionDecisionMISToIFB {
18    target: IntegralFlowBundles,
19    num_source_vertices: usize,
20}
21
22impl ReductionResult for ReductionDecisionMISToIFB {
23    type Source = Decision<MaximumIndependentSet<SimpleGraph, One>>;
24    type Target = IntegralFlowBundles;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        let feasible =
35            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
36        if !feasible.0 {
37            return Err(crate::rules::ExtractionError::invalid(
38                "target flow must satisfy conservation, bundle capacities, and the requirement",
39            ));
40        }
41        Ok((0..self.num_source_vertices)
42            .map(|i| target_solution[2 * i + 1] == 1)
43            .collect())
44    }
45}
46
47/// Check all graph and bundle allocation counts before constructing the network.
48fn flow_dimensions(
49    n: usize,
50    m: usize,
51) -> Result<(usize, usize, usize), crate::rules::ReductionError> {
52    n.checked_add(3)
53        .zip(n.checked_add(1).and_then(|count| count.checked_mul(2)))
54        .zip(n.checked_add(m).and_then(|count| count.checked_add(1)))
55        .map(|((vertices, arcs), bundles)| (vertices, arcs, bundles))
56        .ok_or_else(|| {
57            crate::rules::ReductionError::integer_overflow::<
58                Decision<MaximumIndependentSet<SimpleGraph, One>>,
59                IntegralFlowBundles,
60            >("counting independent-set flow paths and bundles")
61        })
62}
63
64/// Thresholds outside [0,n] have constant truth values for cardinality decisions.
65/// Map them to 0 and n+1, then account for the auxiliary unit of flow.
66fn flow_requirement(n: usize, bound: i64) -> Result<i64, crate::rules::ReductionError> {
67    let n = <Decision<MaximumIndependentSet<SimpleGraph, One>> as ReduceTo<
68        IntegralFlowBundles,
69    >>::exact_i64(n, "converting the independent-set vertex count")?;
70    let maximum_requirement = n.checked_add(2).ok_or_else(|| {
71        crate::rules::ReductionError::integer_overflow::<
72            Decision<MaximumIndependentSet<SimpleGraph, One>>,
73            IntegralFlowBundles,
74        >("shifting the independent-set decision threshold")
75    })?;
76    Ok(bound.clamp(0, maximum_requirement - 1) + 1)
77}
78
79#[reduction(
80    transform = exact {
81        num_vertices = "num_vertices + 3",
82        num_arcs = "2 * num_vertices + 2",
83        num_bundles = "num_edges + num_vertices + 1",
84    }
85)]
86impl ReduceTo<IntegralFlowBundles> for Decision<MaximumIndependentSet<SimpleGraph, One>> {
87    type Result = ReductionDecisionMISToIFB;
88
89    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
90        let graph = self.inner().graph();
91        let n = graph.num_vertices();
92        let (num_vertices, num_arcs, num_bundles) = flow_dimensions(n, graph.num_edges())?;
93        let requirement = flow_requirement(n, *self.bound())?;
94        let sink = n + 2;
95        let mut arcs = Vec::with_capacity(num_arcs);
96        // The final path is auxiliary; the other n paths represent source vertices.
97        for i in 0..=n {
98            arcs.push((0, i + 1));
99            arcs.push((i + 1, sink));
100        }
101        let mut bundles = Vec::with_capacity(num_bundles);
102        let mut capacities = Vec::with_capacity(num_bundles);
103        // Mixing incoming/outgoing arcs keeps the two bundle members distinct
104        // even for a self-loop. Conservation makes its constraint 2*f_i <= 1.
105        for (u, v) in graph.edges() {
106            bundles.push(vec![2 * u, 2 * v + 1]);
107            capacities.push(1);
108        }
109        for i in 0..=n {
110            bundles.push(vec![2 * i, 2 * i + 1]);
111            capacities.push(2);
112        }
113        let target = IntegralFlowBundles::new(
114            crate::topology::DirectedGraph::new(num_vertices, arcs),
115            0,
116            sink,
117            bundles,
118            capacities,
119            requirement,
120        );
121        Ok(ReductionDecisionMISToIFB {
122            target,
123            num_source_vertices: n,
124        })
125    }
126}
127
128#[cfg(feature = "example-db")]
129pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
130    use crate::export::SolutionPair;
131    use crate::solvers::BruteForce;
132    vec![crate::example_db::specs::RuleExampleSpec {
133        id: "decisionmaximumindependentset_to_integralflowbundles",
134        build: || {
135            let source = Decision::new(
136                MaximumIndependentSet::new(SimpleGraph::path(3), vec![One; 3]),
137                2,
138            );
139            let reduction = ReduceTo::<IntegralFlowBundles>::reduce_to(&source)
140                .expect("canonical reduction must succeed");
141            let target_witness = BruteForce::new()
142                .solve(reduction.target_problem())
143                .expect("canonical target evaluation must succeed")
144                .expect("the path has an independent set of size two");
145            let source_witness = reduction.extract_solution(&target_witness).unwrap();
146            crate::example_db::specs::assemble_rule_example(
147                &source,
148                reduction.target_problem(),
149                vec![SolutionPair {
150                    source_config: serde_json::json!(source_witness),
151                    target_config: serde_json::json!(target_witness),
152                }],
153            )
154        },
155    }]
156}
157
158#[cfg(test)]
159#[path = "../unit_tests/rules/decisionmaximumindependentset_integralflowbundles.rs"]
160mod tests;
problemreductions/rules/decisionmaximumindependentset_integralflowbundles.rs

problemreductions/rules/
decisionmaximumindependentset_integralflowbundles.rs
