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        crate::rules::traits::validate_target_witness(
35            self.target_problem(),
36            target_solution,
37            |feasible| feasible.0,
38            "target flow must satisfy conservation, bundle capacities, and the requirement",
39        )?;
40        Ok((0..self.num_source_vertices)
41            .map(|i| target_solution[2 * i + 1] == 1)
42            .collect())
43    }
44}
45
46/// Check all graph and bundle allocation counts before constructing the network.
47fn flow_dimensions(
48    n: usize,
49    m: usize,
50) -> Result<(usize, usize, usize), crate::rules::ReductionError> {
51    n.checked_add(3)
52        .zip(n.checked_add(1).and_then(|count| count.checked_mul(2)))
53        .zip(n.checked_add(m).and_then(|count| count.checked_add(1)))
54        .map(|((vertices, arcs), bundles)| (vertices, arcs, bundles))
55        .ok_or_else(|| {
56            crate::rules::ReductionError::integer_overflow::<
57                Decision<MaximumIndependentSet<SimpleGraph, One>>,
58                IntegralFlowBundles,
59            >("counting independent-set flow paths and bundles")
60        })
61}
62
63/// Thresholds outside [0,n] have constant truth values for cardinality decisions.
64/// Map them to 0 and n+1, then account for the auxiliary unit of flow.
65fn flow_requirement(n: usize, bound: i64) -> Result<i64, crate::rules::ReductionError> {
66    let n = <Decision<MaximumIndependentSet<SimpleGraph, One>> as ReduceTo<
67        IntegralFlowBundles,
68    >>::exact_i64(n, "converting the independent-set vertex count")?;
69    let maximum_requirement = n.checked_add(2).ok_or_else(|| {
70        crate::rules::ReductionError::integer_overflow::<
71            Decision<MaximumIndependentSet<SimpleGraph, One>>,
72            IntegralFlowBundles,
73        >("shifting the independent-set decision threshold")
74    })?;
75    Ok(bound.clamp(0, maximum_requirement - 1) + 1)
76}
77
78#[crate::aggregate_reduction(identity)]
79impl crate::rules::AggregateReductionResult for ReductionDecisionMISToIFB {}
80
81#[reduction(
82    transform = exact {
83        max_capacity_bits = "2",
84        num_vertices = "num_vertices + 3",
85        num_arcs = "2 * num_vertices + 2",
86        num_bundles = "num_edges + num_vertices + 1",
87    }
88)]
89impl ReduceTo<IntegralFlowBundles> for Decision<MaximumIndependentSet<SimpleGraph, One>> {
90    type Result = ReductionDecisionMISToIFB;
91
92    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
93        let graph = self.inner().graph();
94        let n = graph.num_vertices();
95        let (num_vertices, num_arcs, num_bundles) = flow_dimensions(n, graph.num_edges())?;
96        let requirement = flow_requirement(n, *self.bound())?;
97        let sink = n + 2;
98        let mut arcs = Vec::with_capacity(num_arcs);
99        // The final path is auxiliary; the other n paths represent source vertices.
100        for i in 0..=n {
101            arcs.push((0, i + 1));
102            arcs.push((i + 1, sink));
103        }
104        let mut bundles = Vec::with_capacity(num_bundles);
105        let mut capacities = Vec::with_capacity(num_bundles);
106        // Mixing incoming/outgoing arcs keeps the two bundle members distinct
107        // even for a self-loop. Conservation makes its constraint 2*f_i <= 1.
108        for (u, v) in graph.edges() {
109            bundles.push(vec![2 * u, 2 * v + 1]);
110            capacities.push(1);
111        }
112        for i in 0..=n {
113            bundles.push(vec![2 * i, 2 * i + 1]);
114            capacities.push(2);
115        }
116        let target = IntegralFlowBundles::new(
117            crate::topology::DirectedGraph::new(num_vertices, arcs),
118            0,
119            sink,
120            bundles,
121            capacities,
122            requirement,
123        );
124        Ok(ReductionDecisionMISToIFB {
125            target,
126            num_source_vertices: n,
127        })
128    }
129}
130
131#[cfg(feature = "example-db")]
132pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
133    use crate::export::SolutionPair;
134    use crate::solvers::BruteForce;
135    vec![crate::example_db::specs::RuleExampleSpec {
136        id: "decisionmaximumindependentset_to_integralflowbundles",
137        build: || {
138            let source = Decision::new(
139                MaximumIndependentSet::new(SimpleGraph::path(3), vec![One; 3]),
140                2,
141            );
142            let reduction = ReduceTo::<IntegralFlowBundles>::reduce_to(&source)
143                .expect("canonical reduction must succeed");
144            let target_witness = BruteForce::new()
145                .solve(reduction.target_problem())
146                .expect("canonical target evaluation must succeed")
147                .expect("the path has an independent set of size two");
148            let source_witness = reduction.extract_solution(&target_witness).unwrap();
149            crate::example_db::specs::assemble_rule_example(
150                &source,
151                reduction.target_problem(),
152                vec![SolutionPair {
153                    source_config: serde_json::json!(source_witness),
154                    target_config: serde_json::json!(target_witness),
155                }],
156            )
157        },
158    }]
159}
160
161#[cfg(test)]
162#[path = "../unit_tests/rules/decisionmaximumindependentset_integralflowbundles.rs"]
163mod tests;
problemreductions/rules/decisionmaximumindependentset_integralflowbundles.rs

problemreductions/rules/
decisionmaximumindependentset_integralflowbundles.rs
