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::One;
13
14/// The source vertices precede the two mandatory auxiliary centers.
15#[derive(Debug, Clone)]
16pub struct ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
17    target: Decision<MinMaxMulticenter<SimpleGraph, One>>,
18    source_num_vertices: usize,
19}
20
21impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
22    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
23    type Target = Decision<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        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target placement does not certify a dominating set: radius must be at most one",
38        )?;
39        Ok(target_solution[..self.source_num_vertices].to_vec())
40    }
41}
42
43#[crate::aggregate_reduction(identity)]
44impl crate::rules::AggregateReductionResult
45    for ReductionDecisionMinimumDominatingSetToMinMaxMulticenter
46{
47}
48
49#[reduction(
50    transform = exact {
51        max_numeric_magnitude_bits = "1",
52        num_vertices = "num_vertices + 2",
53        num_edges = "num_edges",
54    }
55)]
56impl ReduceTo<Decision<MinMaxMulticenter<SimpleGraph, One>>>
57    for Decision<MinimumDominatingSet<SimpleGraph, One>>
58{
59    type Result = ReductionDecisionMinimumDominatingSetToMinMaxMulticenter;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let source_graph = self.inner().graph();
63        let n = source_graph.num_vertices();
64        let (target_n, centers) = multicenter_parameters(n, *self.bound())?;
65        let target = MinMaxMulticenter::new(
66            SimpleGraph::new(target_n, source_graph.edges()),
67            vec![One; target_n],
68            vec![One; source_graph.num_edges()],
69            centers,
70        );
71        Ok(ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
72            target: Decision::new(target, 1),
73            source_num_vertices: n,
74        })
75    }
76}
77
78/// Check parameter arithmetic before allocating either graph or weight vectors.
79fn multicenter_parameters(
80    n: usize,
81    bound: i64,
82) -> Result<(usize, usize), crate::rules::ReductionError> {
83    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
84    type Target = Decision<MinMaxMulticenter<SimpleGraph, One>>;
85    let overflow = || {
86        crate::rules::ReductionError::integer_overflow::<Source, Target>(
87            "encoding min-max multicenter parameters",
88        )
89    };
90    let target_n = n.checked_add(2).ok_or_else(overflow)?;
91    let n_i64 = i64::try_from(n).map_err(|_| overflow())?;
92    // Subset sizes lie in [0,n], so all lower bounds share the NO case -1.
93    let normalized = bound.clamp(-1, n_i64);
94    let centers = normalized.checked_add(2).ok_or_else(overflow)?;
95    let centers = usize::try_from(centers).map_err(|_| overflow())?;
96    Ok((target_n, centers))
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "decisionminimumdominatingset_to_minmaxmulticenter",
105        build: || {
106            crate::example_db::specs::rule_example_with_witness::<
107                _,
108                Decision<MinMaxMulticenter<SimpleGraph, One>>,
109            >(
110                Decision::new(
111                    MinimumDominatingSet::new(
112                        SimpleGraph::new(
113                            6,
114                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
115                        ),
116                        vec![One; 6],
117                    ),
118                    2,
119                ),
120                SolutionPair {
121                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
122                    target_config: serde_json::json!(vec![
123                        true, false, false, true, false, false, true, true
124                    ]),
125                },
126            )
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/decisionminimumdominatingset_minmaxmulticenter.rs"]
133mod tests;
problemreductions/rules/decisionminimumdominatingset_minmaxmulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minmaxmulticenter.rs
