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}
18
19impl ReductionResult for ReductionXC3SToMaximumSetPacking {
20    type Source = ExactCoverBy3Sets;
21    type Target = MaximumSetPacking<One>;
22
23    fn target_problem(&self) -> &MaximumSetPacking<One> {
24        &self.target
25    }
26
27    /// Extract X3C solution from MaximumSetPacking solution.
28    ///
29    /// The configuration is identity (same binary selection vector).
30    /// A packing of q disjoint 3-sets over a 3q-element universe is necessarily
31    /// an exact cover, so no additional checking is needed.
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution.to_vec()
34    }
35}
36
37#[reduction(overhead = {
38    num_sets = "num_subsets",
39})]
40impl ReduceTo<MaximumSetPacking<One>> for ExactCoverBy3Sets {
41    type Result = ReductionXC3SToMaximumSetPacking;
42
43    fn reduce_to(&self) -> Self::Result {
44        let sets: Vec<Vec<usize>> = self
45            .subsets()
46            .iter()
47            .map(|triple| triple.to_vec())
48            .collect();
49
50        ReductionXC3SToMaximumSetPacking {
51            target: MaximumSetPacking::<One>::new(sets),
52        }
53    }
54}
55
56#[cfg(feature = "example-db")]
57pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
58    use crate::export::SolutionPair;
59
60    vec![crate::example_db::specs::RuleExampleSpec {
61        id: "exactcoverby3sets_to_maximumsetpacking",
62        build: || {
63            // Universe {0,1,2,3,4,5}, subsets [{0,1,2}, {0,1,3}, {3,4,5}, {2,4,5}, {1,3,5}]
64            // Exact cover: S0={0,1,2} + S2={3,4,5}
65            let source = ExactCoverBy3Sets::new(
66                6,
67                vec![[0, 1, 2], [0, 1, 3], [3, 4, 5], [2, 4, 5], [1, 3, 5]],
68            );
69            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<One>>(
70                source,
71                SolutionPair {
72                    source_config: vec![1, 0, 1, 0, 0],
73                    target_config: vec![1, 0, 1, 0, 0],
74                },
75            )
76        },
77    }]
78}
79
80#[cfg(test)]
81#[path = "../unit_tests/rules/exactcoverby3sets_maximumsetpacking.rs"]
82mod tests;
problemreductions/rules/exactcoverby3sets_maximumsetpacking.rs

problemreductions/rules/
exactcoverby3sets_maximumsetpacking.rs
