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        if !crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?
38            .0
39        {
40            return Err(crate::rules::ExtractionError::invalid(
41                "containment inequality is not satisfied",
42            ));
43        }
44        Ok(target_solution.clone())
45    }
46}
47
48#[reduction(
49    transform = upper_bound {
50        universe_size = "num_vertices",
51        num_r_sets = "num_vertices + 1",
52        num_s_sets = "num_vertices + num_edges + 1",
53    }
54)]
55impl ReduceTo<ComparativeContainment<i64>> for Decision<MinimumVertexCover<SimpleGraph, i64>> {
56    type Result = ReductionDecisionMVCToComparativeContainment;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let overflow = |operation| {
60            crate::rules::ReductionError::integer_overflow::<Self, ComparativeContainment<i64>>(
61                operation,
62            )
63        };
64        let weights = self.inner().weights();
65        let n = self.inner().graph().num_vertices();
66        let mut positive_total = 0i64;
67        let mut negative_total = 0i64;
68        for &weight in weights {
69            if weight > 0 {
70                positive_total = positive_total
71                    .checked_add(weight)
72                    .ok_or_else(|| overflow("summing positive vertex weights"))?;
73            } else {
74                negative_total = negative_total
75                    .checked_add(weight)
76                    .ok_or_else(|| overflow("summing negative vertex weights"))?;
77            }
78        }
79        // All subset sums lie in [negative_total, positive_total].
80        // Opposite-sign operands cannot overflow.
81        let total = positive_total + negative_total;
82        let bound = (*self.bound()).min(positive_total);
83        let constant = bound
84            .checked_sub(total)
85            .ok_or_else(|| overflow("computing the containment budget term"))?;
86        let penalty = positive_total
87            .checked_sub(negative_total)
88            .and_then(|span| span.checked_add(1))
89            .ok_or_else(|| overflow("computing a strict uncovered-edge penalty"))?;
90
91        let mut r_sets = Vec::new();
92        let mut r_weights = Vec::new();
93        let mut s_sets = Vec::new();
94        let mut s_weights = Vec::new();
95        // A signed term is represented on the corresponding side of R >= S.
96        for (set, coefficient) in weights
97            .iter()
98            .enumerate()
99            .filter(|(_, w)| **w != 0)
100            .map(|(v, &w)| (complement_singleton(n, v), w))
101            .chain((constant != 0).then(|| ((0..n).collect(), constant)))
102        {
103            if coefficient > 0 {
104                r_sets.push(set);
105                r_weights.push(coefficient);
106            } else if coefficient < 0 {
107                s_sets.push(set);
108                s_weights.push(
109                    coefficient
110                        .checked_neg()
111                        .ok_or_else(|| overflow("negating a containment coefficient"))?,
112                );
113            }
114        }
115        for (u, v) in self.inner().graph().edges() {
116            s_sets.push(complement_pair(n, u, v));
117            s_weights.push(penalty);
118        }
119        // The empty subset is contained in every set. Checking both full sums
120        // ensures every target evaluation stays in i64, including NO witnesses.
121        for family in [&r_weights, &s_weights] {
122            family
123                .iter()
124                .try_fold(0i64, |sum, &weight| sum.checked_add(weight))
125                .ok_or_else(|| overflow("summing a containment weight family"))?;
126        }
127        let target = ComparativeContainment::with_weights(n, r_sets, s_sets, r_weights, s_weights)
128            .map_err(
129                crate::rules::ReductionError::construction::<Self, ComparativeContainment<i64>>,
130            )?;
131        Ok(ReductionDecisionMVCToComparativeContainment { target })
132    }
133}
134
135fn complement_singleton(n: usize, v: usize) -> Vec<usize> {
136    (0..n).filter(|&x| x != v).collect()
137}
138
139fn complement_pair(n: usize, u: usize, v: usize) -> Vec<usize> {
140    (0..n).filter(|&x| x != u && x != v).collect()
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
145    use crate::export::SolutionPair;
146
147    vec![crate::example_db::specs::RuleExampleSpec {
148        id: "decisionminimumvertexcover_to_comparativecontainment",
149        build: || {
150            // Path P_4: 0-1-2-3, bound K=2. Minimum cover {1,2} has size 2.
151            let inner = MinimumVertexCover::new(
152                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
153                vec![1i64; 4],
154            );
155            let source = Decision::new(inner, 2);
156            crate::example_db::specs::rule_example_with_witness::<_, ComparativeContainment<i64>>(
157                source,
158                SolutionPair {
159                    source_config: serde_json::json!(vec![false, true, true, false]),
160                    target_config: serde_json::json!(vec![false, true, true, false]),
161                },
162            )
163        },
164    }]
165}
166
167#[cfg(test)]
168#[path = "../unit_tests/rules/minimumvertexcover_comparativecontainment.rs"]
169mod tests;
problemreductions/rules/minimumvertexcover_comparativecontainment.rs

problemreductions/rules/
minimumvertexcover_comparativecontainment.rs
