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(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
36
37        let pole_position = target_solution[self.pole];
38        Ok(target_solution[..self.source_universe_size]
39            .iter()
40            .map(|&position| position > pole_position)
41            .collect())
42    }
43}
44
45#[reduction(
46    transform = unavailable {
47        num_elements = "the exact target parameters depend on normalization statistics specific to this reduction",
48        num_triples = "the exact target parameters depend on normalization statistics specific to this reduction",
49    }
50)]
51impl ReduceTo<Betweenness> for SetSplitting {
52    type Result = ReductionSetSplittingToBetweenness;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let (normalized_universe_size, normalized_subsets) = self.normalized_instance();
56        let pole = normalized_universe_size;
57        let size3_subsets = normalized_subsets
58            .iter()
59            .filter(|subset| subset.len() == 3)
60            .count();
61        let mut triples = Vec::with_capacity(normalized_subsets.len() + size3_subsets);
62        let mut num_elements = normalized_universe_size + 1;
63
64        for subset in normalized_subsets {
65            match subset.as_slice() {
66                [u, v] => triples.push((*u, pole, *v)),
67                [u, v, w] => {
68                    let auxiliary = num_elements;
69                    num_elements += 1;
70                    triples.push((*u, auxiliary, *v));
71                    triples.push((auxiliary, pole, *w));
72                }
73                _ => {
74                    return Err(crate::rules::ReductionError::invalid_target::<
75                        SetSplitting,
76                        Betweenness,
77                    >(
78                        "normalized subset must contain two or three elements"
79                    ));
80                }
81            }
82        }
83
84        Ok(ReductionSetSplittingToBetweenness {
85            target: Betweenness::new(num_elements, triples),
86            source_universe_size: self.universe_size(),
87            pole,
88        })
89    }
90}
91
92#[cfg(feature = "example-db")]
93pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
94    use crate::export::SolutionPair;
95
96    vec![crate::example_db::specs::RuleExampleSpec {
97        id: "setsplitting_to_betweenness",
98        build: || {
99            crate::example_db::specs::rule_example_with_witness::<_, Betweenness>(
100                SetSplitting::new(
101                    5,
102                    vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 3, 4], vec![1, 2, 3]],
103                ),
104                SolutionPair {
105                    source_config: serde_json::json!(vec![true, false, true, false, false]),
106                    target_config: serde_json::json!(vec![8, 2, 9, 0, 1, 4, 3, 6, 7, 5]),
107                },
108            )
109        },
110    }]
111}
112
113#[cfg(test)]
114#[path = "../unit_tests/rules/setsplitting_betweenness.rs"]
115mod tests;
problemreductions/rules/setsplitting_betweenness.rs

problemreductions/rules/
setsplitting_betweenness.rs
