problemreductions/rules/
decisionminimumdominatingset_minmaxmulticenter.rs

1//! Reduction from Decision Minimum Dominating Set to Min-Max Multicenter.
2//!
3//! On unit-weight, unit-length graphs, choosing `K` centers with maximum
4//! distance at most `1` is exactly choosing a dominating set of size `K`.
5
6use crate::models::decision::Decision;
7use crate::models::graph::{MinMaxMulticenter, MinimumDominatingSet};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::One;
12
13/// Result of reducing DecisionMinimumDominatingSet to MinMaxMulticenter.
14#[derive(Debug, Clone)]
15pub struct ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
16    target: MinMaxMulticenter<SimpleGraph, One>,
17}
18
19impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinMaxMulticenter {
20    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
21    type Target = MinMaxMulticenter<SimpleGraph, One>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution.to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vertices = "num_vertices",
35        num_edges = "num_edges",
36    }
37)]
38impl ReduceTo<MinMaxMulticenter<SimpleGraph, One>>
39    for Decision<MinimumDominatingSet<SimpleGraph, One>>
40{
41    type Result = ReductionDecisionMinimumDominatingSetToMinMaxMulticenter;
42
43    fn reduce_to(&self) -> Self::Result {
44        let source_graph = self.inner().graph();
45        let target = MinMaxMulticenter::new(
46            SimpleGraph::new(source_graph.num_vertices(), source_graph.edges()),
47            vec![One; source_graph.num_vertices()],
48            vec![One; source_graph.num_edges()],
49            self.k(),
50        );
51        ReductionDecisionMinimumDominatingSetToMinMaxMulticenter { target }
52    }
53}
54
55#[cfg(feature = "example-db")]
56pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
57    use crate::export::SolutionPair;
58
59    vec![crate::example_db::specs::RuleExampleSpec {
60        id: "decisionminimumdominatingset_to_minmaxmulticenter",
61        build: || {
62            crate::example_db::specs::rule_example_with_witness::<
63                _,
64                MinMaxMulticenter<SimpleGraph, One>,
65            >(
66                Decision::new(
67                    MinimumDominatingSet::new(
68                        SimpleGraph::new(
69                            6,
70                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
71                        ),
72                        vec![One; 6],
73                    ),
74                    2,
75                ),
76                SolutionPair {
77                    source_config: vec![1, 0, 0, 1, 0, 0],
78                    target_config: vec![1, 0, 0, 1, 0, 0],
79                },
80            )
81        },
82    }]
83}
84
85#[cfg(test)]
86#[path = "../unit_tests/rules/decisionminimumdominatingset_minmaxmulticenter.rs"]
87mod tests;
problemreductions/rules/decisionminimumdominatingset_minmaxmulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minmaxmulticenter.rs
