problemreductions/rules/
setsplitting_betweenness.rs

1//! Reduction from Set Splitting to Betweenness.
2//!
3//! Deduplicate each subset and decompose sizes above 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//! A singleton becomes two incompatible order constraints, preserving infeasibility.
10
11use crate::models::misc::Betweenness;
12use crate::models::set::SetSplitting;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15
16/// Result of reducing SetSplitting to Betweenness.
17#[derive(Debug, Clone)]
18pub struct ReductionSetSplittingToBetweenness {
19    target: Betweenness,
20    source_universe_size: usize,
21    pole: usize,
22}
23
24impl ReductionResult for ReductionSetSplittingToBetweenness {
25    type Source = SetSplitting;
26    type Target = Betweenness;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_witness(
37            self.target_problem(),
38            target_solution,
39            |value| value.0,
40            "target witness does not satisfy the target problem",
41        )?;
42
43        let pole_position = target_solution[self.pole];
44        Ok(target_solution[..self.source_universe_size]
45            .iter()
46            .map(|&position| position > pole_position)
47            .collect())
48    }
49}
50
51#[crate::aggregate_reduction(identity)]
52impl crate::rules::AggregateReductionResult for ReductionSetSplittingToBetweenness {}
53
54#[reduction(transform = upper_bound {
55    num_elements = "universe_size + 1 + num_subsets * (4 * universe_size + 1)",
56    num_triples = "2 * num_subsets * (2 * universe_size + 1)",
57})]
58impl ReduceTo<Betweenness> for SetSplitting {
59    type Result = ReductionSetSplittingToBetweenness;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let (normalized_universe_size, normalized_subsets) = self.normalized_instance();
63        let pole = normalized_universe_size;
64        let size3_subsets = normalized_subsets
65            .iter()
66            .filter(|subset| subset.len() == 3)
67            .count();
68        let mut triples = Vec::with_capacity(normalized_subsets.len() + size3_subsets);
69        let mut num_elements = normalized_universe_size + 1;
70
71        for subset in normalized_subsets {
72            match subset.as_slice() {
73                [u] => {
74                    // A singleton cannot contain both colors. These orders
75                    // cannot both hold for three distinct elements.
76                    let auxiliary = num_elements;
77                    num_elements += 1;
78                    triples.push((*u, pole, auxiliary));
79                    triples.push((pole, *u, auxiliary));
80                }
81                [u, v] => triples.push((*u, pole, *v)),
82                [u, v, w] => {
83                    let auxiliary = num_elements;
84                    num_elements += 1;
85                    triples.push((*u, auxiliary, *v));
86                    triples.push((auxiliary, pole, *w));
87                }
88                _ => {
89                    return Err(crate::rules::ReductionError::invalid_target::<
90                        SetSplitting,
91                        Betweenness,
92                    >(
93                        "normalized subset must contain one, two or three elements",
94                    ));
95                }
96            }
97        }
98
99        Ok(ReductionSetSplittingToBetweenness {
100            target: Betweenness::new(num_elements, triples),
101            source_universe_size: self.universe_size(),
102            pole,
103        })
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    use crate::export::SolutionPair;
110
111    vec![crate::example_db::specs::RuleExampleSpec {
112        id: "setsplitting_to_betweenness",
113        build: || {
114            crate::example_db::specs::rule_example_with_witness::<_, Betweenness>(
115                SetSplitting::new(
116                    5,
117                    vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 3, 4], vec![1, 2, 3]],
118                ),
119                SolutionPair {
120                    source_config: serde_json::json!(vec![true, false, true, false, false]),
121                    target_config: serde_json::json!(vec![8, 2, 9, 0, 1, 4, 3, 6, 7, 5]),
122                },
123            )
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/setsplitting_betweenness.rs"]
130mod tests;
problemreductions/rules/setsplitting_betweenness.rs

problemreductions/rules/
setsplitting_betweenness.rs
