problemreductions/rules/
decisionminimumdominatingset_minimumsummulticenter.rs

1//! Reduction from Decision Minimum Dominating Set to Minimum Sum Multicenter.
2//!
3//! For K >= 0, add an isolated vertex and choose min(K, n) + 1 centers.
4//! Finite cost forces the isolated vertex to be a center. The optimum equals
5//! n - min(K, n) iff the original graph has a dominating set of size <= K.
6//! For K < 0, two added isolated vertices and one center force infeasibility.
7
8use crate::models::decision::Decision;
9use crate::models::graph::{MinimumDominatingSet, MinimumSumMulticenter};
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13use crate::types::{Min, One, Or};
14
15/// Result of reducing DecisionMinimumDominatingSet to MinimumSumMulticenter.
16#[derive(Debug, Clone)]
17pub struct ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
18    target: MinimumSumMulticenter<SimpleGraph, i64>,
19    source_num_vertices: usize,
20    threshold: i64,
21}
22
23impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
24    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
25    type Target = MinimumSumMulticenter<SimpleGraph, i64>;
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        let value =
36            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37        if !crate::rules::AggregateReductionResult::extract_value(self, value).0 {
38            return Err(crate::rules::ExtractionError::invalid(
39                "target placement does not certify a dominating set within the source bound",
40            ));
41        }
42        // Original vertices precede the auxiliary isolated vertices.
43        Ok(target_solution[..self.source_num_vertices].to_vec())
44    }
45}
46
47impl crate::rules::AggregateReductionResult
48    for ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter
49{
50    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
51    type Target = MinimumSumMulticenter<SimpleGraph, i64>;
52
53    fn target_problem(&self) -> &Self::Target {
54        &self.target
55    }
56
57    fn extract_value(&self, target_value: Min<i64>) -> Or {
58        Or(target_value.0 == Some(self.threshold))
59    }
60}
61
62#[reduction(
63    aggregate = custom,
64    transform = upper_bound { num_vertices = "num_vertices + 2", num_edges = "num_edges" }
65)]
66impl ReduceTo<MinimumSumMulticenter<SimpleGraph, i64>>
67    for Decision<MinimumDominatingSet<SimpleGraph, One>>
68{
69    type Result = ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter;
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, threshold) = multicenter_parameters(n, *self.bound())?;
75        let target = MinimumSumMulticenter::new(
76            SimpleGraph::new(target_n, source_graph.edges()),
77            vec![1i64; target_n],
78            vec![1i64; source_graph.num_edges()],
79            centers,
80        );
81        Ok(
82            ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
83                target,
84                source_num_vertices: n,
85                threshold,
86            },
87        )
88    }
89}
90
91/// Compute the construction's counts without allocating the graph, so numeric
92/// domain boundaries can be checked independently of available memory.
93fn multicenter_parameters(
94    n: usize,
95    bound: i64,
96) -> Result<(usize, usize, i64), crate::rules::ReductionError> {
97    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
98    type Target = MinimumSumMulticenter<SimpleGraph, i64>;
99    let overflow = || {
100        crate::rules::ReductionError::integer_overflow::<Source, Target>(
101            "encoding multicenter construction parameters",
102        )
103    };
104    let extra_vertices = if bound < 0 { 2 } else { 1 };
105    let target_n = n.checked_add(extra_vertices).ok_or_else(overflow)?;
106    let n_i64 = i64::try_from(n).map_err(|_| overflow())?;
107    if bound < 0 {
108        // Two auxiliary isolates cannot both be served by one center.
109        return Ok((target_n, 1, -1));
110    }
111    // No subset contains more than n vertices, so these bounds are equivalent.
112    let q = bound.min(n_i64);
113    let q_usize = usize::try_from(q).map_err(|_| overflow())?;
114    // q <= n and n + 1 was checked above, so q + 1 cannot overflow.
115    Ok((target_n, q_usize + 1, n_i64 - q))
116}
117
118#[cfg(feature = "example-db")]
119pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
120    use crate::export::SolutionPair;
121
122    vec![crate::example_db::specs::RuleExampleSpec {
123        id: "decisionminimumdominatingset_to_minimumsummulticenter",
124        build: || {
125            crate::example_db::specs::rule_example_with_witness::<
126                _,
127                MinimumSumMulticenter<SimpleGraph, i64>,
128            >(
129                Decision::new(
130                    MinimumDominatingSet::new(
131                        SimpleGraph::new(
132                            6,
133                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
134                        ),
135                        vec![One; 6],
136                    ),
137                    2,
138                ),
139                SolutionPair {
140                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
141                    target_config: serde_json::json!(vec![
142                        true, false, false, true, false, false, true
143                    ]),
144                },
145            )
146        },
147    }]
148}
149
150#[cfg(test)]
151#[path = "../unit_tests/rules/decisionminimumdominatingset_minimumsummulticenter.rs"]
152mod tests;
problemreductions/rules/decisionminimumdominatingset_minimumsummulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minimumsummulticenter.rs
