problemreductions/rules/
setsplitting_betweenness.rs

1//! Reduction from Set Splitting to Betweenness.
2//!
3//! Decompose each subset to size 2 or 3 using complementarity pairs, then
4//! place a single pole element `p` in the Betweenness instance. A size-2
5//! subset `{u, v}` becomes `(u, p, v)`, forcing opposite sides of the pole.
6//! A size-3 subset `{u, v, w}` becomes `(u, d, v)` and `(d, p, w)` with one
7//! fresh auxiliary element `d`, which is satisfiable exactly when the three
8//! elements are not monochromatic with respect to the pole.
9
10use crate::models::misc::Betweenness;
11use crate::models::set::SetSplitting;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing SetSplitting to Betweenness.
16#[derive(Debug, Clone)]
17pub struct ReductionSetSplittingToBetweenness {
18    target: Betweenness,
19    source_universe_size: usize,
20    pole: usize,
21}
22
23impl ReductionResult for ReductionSetSplittingToBetweenness {
24    type Source = SetSplitting;
25    type Target = Betweenness;
26
27    fn target_problem(&self) -> &Self::Target {
28        &self.target
29    }
30
31    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
32        assert!(
33            target_solution.len() > self.pole,
34            "Betweenness solution has {} positions but pole index is {}",
35            target_solution.len(),
36            self.pole
37        );
38        assert!(
39            target_solution.len() >= self.source_universe_size,
40            "Betweenness solution has {} positions but source requires {} elements",
41            target_solution.len(),
42            self.source_universe_size
43        );
44
45        let pole_position = target_solution[self.pole];
46        target_solution[..self.source_universe_size]
47            .iter()
48            .map(|&position| usize::from(position > pole_position))
49            .collect()
50    }
51}
52
53#[reduction(
54    overhead = {
55        num_elements = "normalized_universe_size + 1 + normalized_num_size3_subsets",
56        num_triples = "normalized_num_size2_subsets + 2 * normalized_num_size3_subsets",
57    }
58)]
59impl ReduceTo<Betweenness> for SetSplitting {
60    type Result = ReductionSetSplittingToBetweenness;
61
62    fn reduce_to(&self) -> Self::Result {
63        let (normalized_universe_size, normalized_subsets) = self.normalized_instance();
64        let pole = normalized_universe_size;
65        let size3_subsets = normalized_subsets
66            .iter()
67            .filter(|subset| subset.len() == 3)
68            .count();
69        let mut triples = Vec::with_capacity(normalized_subsets.len() + size3_subsets);
70        let mut num_elements = normalized_universe_size + 1;
71
72        for subset in normalized_subsets {
73            match subset.as_slice() {
74                [u, v] => triples.push((*u, pole, *v)),
75                [u, v, w] => {
76                    let auxiliary = num_elements;
77                    num_elements += 1;
78                    triples.push((*u, auxiliary, *v));
79                    triples.push((auxiliary, pole, *w));
80                }
81                _ => unreachable!("normalization only produces size-2 or size-3 subsets"),
82            }
83        }
84
85        ReductionSetSplittingToBetweenness {
86            target: Betweenness::new(num_elements, triples),
87            source_universe_size: self.universe_size(),
88            pole,
89        }
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::export::SolutionPair;
96
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "setsplitting_to_betweenness",
99        build: || {
100            crate::example_db::specs::rule_example_with_witness::<_, Betweenness>(
101                SetSplitting::new(
102                    5,
103                    vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 3, 4], vec![1, 2, 3]],
104                ),
105                SolutionPair {
106                    source_config: vec![1, 0, 1, 0, 0],
107                    target_config: vec![8, 2, 9, 0, 1, 4, 3, 6, 7, 5],
108                },
109            )
110        },
111    }]
112}
113
114#[cfg(test)]
115#[path = "../unit_tests/rules/setsplitting_betweenness.rs"]
116mod tests;
problemreductions/rules/setsplitting_betweenness.rs

problemreductions/rules/
setsplitting_betweenness.rs
