problemreductions/rules/
decisionminimumdominatingset_minmaxmulticenter.rs

1//! Unit decision dominating set to min-max multicenter.
2//!
3//! Add two isolated vertices and use clamp(K,-1,n)+2 centers. Every finite
4//! placement selects both isolates; radius <= 1 is then exactly the source
5//! dominating-set threshold. This includes empty graphs and every signed K.
6
7use crate::models::decision::Decision;
8use crate::models::graph::{MinMaxMulticenter, MinimumDominatingSet};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use crate::types::{Min, One, Or};
13
14/// The source vertices precede the two mandatory auxiliary centers.
15#[derive(Debug, Clone)]
16pub struct ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
17    target: MinMaxMulticenter<SimpleGraph, One>,
18    source_num_vertices: usize,
19}
20
21impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
22    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
23    type Target = MinMaxMulticenter<SimpleGraph, One>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        let value =
34            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
35        if !crate::rules::AggregateReductionResult::extract_value(self, value).0 {
36            return Err(crate::rules::ExtractionError::invalid(
37                "target placement does not certify a dominating set: radius must be at most one",
38            ));
39        }
40        Ok(target_solution[..self.source_num_vertices].to_vec())
41    }
42}
43
44impl crate::rules::AggregateReductionResult
45    for ReductionDecisionMinimumDominatingSetToMinMaxMulticenter
46{
47    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
48    type Target = MinMaxMulticenter<SimpleGraph, One>;
49
50    fn target_problem(&self) -> &Self::Target {
51        &self.target
52    }
53
54    fn extract_value(&self, target_value: Min<i64>) -> Or {
55        Or(target_value.0.is_some_and(|radius| radius <= 1))
56    }
57}
58
59#[reduction(
60    aggregate = custom,
61    transform = exact {
62        num_vertices = "num_vertices + 2",
63        num_edges = "num_edges",
64    }
65)]
66impl ReduceTo<MinMaxMulticenter<SimpleGraph, One>>
67    for Decision<MinimumDominatingSet<SimpleGraph, One>>
68{
69    type Result = ReductionDecisionMinimumDominatingSetToMinMaxMulticenter;
70
71    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
72        let source_graph = self.inner().graph();
73        let n = source_graph.num_vertices();
74        let (target_n, centers) = multicenter_parameters(n, *self.bound())?;
75        let target = MinMaxMulticenter::new(
76            SimpleGraph::new(target_n, source_graph.edges()),
77            vec![One; target_n],
78            vec![One; source_graph.num_edges()],
79            centers,
80        );
81        Ok(ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
82            target,
83            source_num_vertices: n,
84        })
85    }
86}
87
88/// Check parameter arithmetic before allocating either graph or weight vectors.
89fn multicenter_parameters(
90    n: usize,
91    bound: i64,
92) -> Result<(usize, usize), crate::rules::ReductionError> {
93    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
94    type Target = MinMaxMulticenter<SimpleGraph, One>;
95    let overflow = || {
96        crate::rules::ReductionError::integer_overflow::<Source, Target>(
97            "encoding min-max multicenter parameters",
98        )
99    };
100    let target_n = n.checked_add(2).ok_or_else(overflow)?;
101    let n_i64 = i64::try_from(n).map_err(|_| overflow())?;
102    // Subset sizes lie in [0,n], so all lower bounds share the NO case -1.
103    let normalized = bound.clamp(-1, n_i64);
104    let centers = normalized.checked_add(2).ok_or_else(overflow)?;
105    let centers = usize::try_from(centers).map_err(|_| overflow())?;
106    Ok((target_n, centers))
107}
108
109#[cfg(feature = "example-db")]
110pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
111    use crate::export::SolutionPair;
112
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "decisionminimumdominatingset_to_minmaxmulticenter",
115        build: || {
116            crate::example_db::specs::rule_example_with_witness::<
117                _,
118                MinMaxMulticenter<SimpleGraph, One>,
119            >(
120                Decision::new(
121                    MinimumDominatingSet::new(
122                        SimpleGraph::new(
123                            6,
124                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
125                        ),
126                        vec![One; 6],
127                    ),
128                    2,
129                ),
130                SolutionPair {
131                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
132                    target_config: serde_json::json!(vec![
133                        true, false, false, true, false, false, true, true
134                    ]),
135                },
136            )
137        },
138    }]
139}
140
141#[cfg(test)]
142#[path = "../unit_tests/rules/decisionminimumdominatingset_minmaxmulticenter.rs"]
143mod tests;
problemreductions/rules/decisionminimumdominatingset_minmaxmulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minmaxmulticenter.rs
