problemreductions/rules/
exactcoverby3sets_maximumsetpacking.rs

1//! Reduction from ExactCoverBy3Sets to MaximumSetPacking.
2//!
3//! Given an X3C instance with universe X (|X| = 3q) and collection C of
4//! 3-element subsets, construct a `MaximumSetPacking<One>` instance where each
5//! triple becomes a variable-length set with unit weight. An exact cover
6//! of q disjoint triples corresponds to a maximum packing of value q.
7
8use crate::models::set::{ExactCoverBy3Sets, MaximumSetPacking};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::types::One;
12
13/// Result of reducing ExactCoverBy3Sets to MaximumSetPacking<One>.
14#[derive(Debug, Clone)]
15pub struct ReductionXC3SToMaximumSetPacking {
16    target: MaximumSetPacking<One>,
17    source_universe_size: usize,
18}
19
20impl ReductionResult for ReductionXC3SToMaximumSetPacking {
21    type Source = ExactCoverBy3Sets;
22    type Target = MaximumSetPacking<One>;
23
24    fn target_problem(&self) -> &MaximumSetPacking<One> {
25        &self.target
26    }
27
28    /// Extract X3C solution from MaximumSetPacking solution.
29    ///
30    /// The configuration is identity (same binary selection vector).
31    /// A packing of q disjoint 3-sets over a 3q-element universe is necessarily
32    /// an exact cover, so no additional checking is needed.
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| crate::rules::AggregateReductionResult::extract_value(self, value).0,
41            "target witness does not certify a YES answer for the source",
42        )?;
43
44        Ok(target_solution.to_vec())
45    }
46}
47
48#[crate::aggregate_reduction]
49impl crate::rules::AggregateReductionResult for ReductionXC3SToMaximumSetPacking {
50    type Source = ExactCoverBy3Sets;
51    type Target = MaximumSetPacking<One>;
52
53    fn target_problem(&self) -> &Self::Target {
54        &self.target
55    }
56
57    fn extract_value(&self, value: crate::types::Max<i64>) -> crate::types::Or {
58        crate::types::Or(
59            value
60                .0
61                .is_some_and(|count| i128::from(count) == self.source_universe_size as i128 / 3),
62        )
63    }
64}
65
66#[reduction(transform = {
67    exact {
68        num_sets = "num_subsets",
69    },
70    upper_bound {
71        universe_size = "universe_size",
72    },
73})]
74impl ReduceTo<MaximumSetPacking<One>> for ExactCoverBy3Sets {
75    type Result = ReductionXC3SToMaximumSetPacking;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let sets: Vec<Vec<usize>> = self
79            .subsets()
80            .iter()
81            .map(|triple| triple.to_vec())
82            .collect();
83
84        Ok(ReductionXC3SToMaximumSetPacking {
85            target: MaximumSetPacking::<One>::new(sets),
86            source_universe_size: self.universe_size(),
87        })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    use crate::export::SolutionPair;
94
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "exactcoverby3sets_to_maximumsetpacking",
97        build: || {
98            // Universe {0,1,2,3,4,5}, subsets [{0,1,2}, {0,1,3}, {3,4,5}, {2,4,5}, {1,3,5}]
99            // Exact cover: S0={0,1,2} + S2={3,4,5}
100            let source = ExactCoverBy3Sets::new(
101                6,
102                vec![[0, 1, 2], [0, 1, 3], [3, 4, 5], [2, 4, 5], [1, 3, 5]],
103            );
104            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<One>>(
105                source,
106                SolutionPair {
107                    source_config: serde_json::json!(vec![true, false, true, false, false]),
108                    target_config: serde_json::json!(vec![true, false, true, false, false]),
109                },
110            )
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/exactcoverby3sets_maximumsetpacking.rs"]
117mod tests;
problemreductions/rules/exactcoverby3sets_maximumsetpacking.rs

problemreductions/rules/
exactcoverby3sets_maximumsetpacking.rs
