problemreductions/rules/
minimumvertexcover_comparativecontainment.rs

1//! Signed-weight decision vertex cover to comparative containment.
2//!
3//! Extends the complement-set construction cited in Garey--Johnson SP10.
4//! Let W = sum w_v, U = sum max(w_v,0), B = min(K,U), and
5//! P = 1 + sum |w_v|. Encode the signed containment expression
6//! B - W + sum w_v [Y subset V\{v}] - P sum_e [Y subset V\e].
7//! Positive terms go to R, negative terms to S, and zero terms are omitted.
8//! Its value is B - w(Y) - P * uncovered(Y), so it is nonnegative exactly
9//! for vertex covers meeting the bound. Extraction is the identity.
10//! Stored weights and family totals must fit the repository's i64 contract.
11
12use crate::models::decision::Decision;
13use crate::models::graph::MinimumVertexCover;
14use crate::models::set::ComparativeContainment;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17use crate::topology::{Graph, SimpleGraph};
18
19/// Identity witness map for the signed-weight containment construction.
20#[derive(Debug, Clone)]
21pub struct ReductionDecisionMVCToComparativeContainment {
22    target: ComparativeContainment<i64>,
23}
24
25impl ReductionResult for ReductionDecisionMVCToComparativeContainment {
26    type Source = Decision<MinimumVertexCover<SimpleGraph, i64>>;
27    type Target = ComparativeContainment<i64>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_witness(
38            self.target_problem(),
39            target_solution,
40            |value| value.0,
41            "containment inequality is not satisfied",
42        )?;
43        Ok(target_solution.clone())
44    }
45}
46
47#[crate::aggregate_reduction(identity)]
48impl crate::rules::AggregateReductionResult for ReductionDecisionMVCToComparativeContainment {}
49
50#[reduction(
51    transform = upper_bound {
52        universe_size = "num_vertices",
53        num_r_sets = "num_vertices + 1",
54        num_s_sets = "num_vertices + num_edges + 1",
55    }
56)]
57impl ReduceTo<ComparativeContainment<i64>> for Decision<MinimumVertexCover<SimpleGraph, i64>> {
58    type Result = ReductionDecisionMVCToComparativeContainment;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let overflow = |operation| {
62            crate::rules::ReductionError::integer_overflow::<Self, ComparativeContainment<i64>>(
63                operation,
64            )
65        };
66        let weights = self.inner().weights();
67        let n = self.inner().graph().num_vertices();
68        let mut positive_total = 0i64;
69        let mut negative_total = 0i64;
70        for &weight in weights {
71            if weight > 0 {
72                positive_total = positive_total
73                    .checked_add(weight)
74                    .ok_or_else(|| overflow("summing positive vertex weights"))?;
75            } else {
76                negative_total = negative_total
77                    .checked_add(weight)
78                    .ok_or_else(|| overflow("summing negative vertex weights"))?;
79            }
80        }
81        // All subset sums lie in [negative_total, positive_total].
82        // Opposite-sign operands cannot overflow.
83        let total = positive_total + negative_total;
84        let bound = (*self.bound()).min(positive_total);
85        let constant = bound
86            .checked_sub(total)
87            .ok_or_else(|| overflow("computing the containment budget term"))?;
88        let penalty = positive_total
89            .checked_sub(negative_total)
90            .and_then(|span| span.checked_add(1))
91            .ok_or_else(|| overflow("computing a strict uncovered-edge penalty"))?;
92
93        let mut r_sets = Vec::new();
94        let mut r_weights = Vec::new();
95        let mut s_sets = Vec::new();
96        let mut s_weights = Vec::new();
97        // A signed term is represented on the corresponding side of R >= S.
98        for (set, coefficient) in weights
99            .iter()
100            .enumerate()
101            .filter(|(_, w)| **w != 0)
102            .map(|(v, &w)| (complement_singleton(n, v), w))
103            .chain((constant != 0).then(|| ((0..n).collect(), constant)))
104        {
105            if coefficient > 0 {
106                r_sets.push(set);
107                r_weights.push(coefficient);
108            } else if coefficient < 0 {
109                s_sets.push(set);
110                s_weights.push(
111                    coefficient
112                        .checked_neg()
113                        .ok_or_else(|| overflow("negating a containment coefficient"))?,
114                );
115            }
116        }
117        for (u, v) in self.inner().graph().edges() {
118            s_sets.push(complement_pair(n, u, v));
119            s_weights.push(penalty);
120        }
121        // The empty subset is contained in every set. Checking both full sums
122        // ensures every target evaluation stays in i64, including NO witnesses.
123        for family in [&r_weights, &s_weights] {
124            family
125                .iter()
126                .try_fold(0i64, |sum, &weight| sum.checked_add(weight))
127                .ok_or_else(|| overflow("summing a containment weight family"))?;
128        }
129        let target = ComparativeContainment::with_weights(n, r_sets, s_sets, r_weights, s_weights)
130            .map_err(
131                crate::rules::ReductionError::construction::<Self, ComparativeContainment<i64>>,
132            )?;
133        Ok(ReductionDecisionMVCToComparativeContainment { target })
134    }
135}
136
137fn complement_singleton(n: usize, v: usize) -> Vec<usize> {
138    (0..n).filter(|&x| x != v).collect()
139}
140
141fn complement_pair(n: usize, u: usize, v: usize) -> Vec<usize> {
142    (0..n).filter(|&x| x != u && x != v).collect()
143}
144
145#[cfg(feature = "example-db")]
146pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
147    use crate::export::SolutionPair;
148
149    vec![crate::example_db::specs::RuleExampleSpec {
150        id: "decisionminimumvertexcover_to_comparativecontainment",
151        build: || {
152            // Path P_4: 0-1-2-3, bound K=2. Minimum cover {1,2} has size 2.
153            let inner = MinimumVertexCover::new(
154                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
155                vec![1i64; 4],
156            );
157            let source = Decision::new(inner, 2);
158            crate::example_db::specs::rule_example_with_witness::<_, ComparativeContainment<i64>>(
159                source,
160                SolutionPair {
161                    source_config: serde_json::json!(vec![false, true, true, false]),
162                    target_config: serde_json::json!(vec![false, true, true, false]),
163                },
164            )
165        },
166    }]
167}
168
169#[cfg(test)]
170#[path = "../unit_tests/rules/minimumvertexcover_comparativecontainment.rs"]
171mod tests;
problemreductions/rules/minimumvertexcover_comparativecontainment.rs

problemreductions/rules/
minimumvertexcover_comparativecontainment.rs
