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::One;
14
15/// Result of reducing DecisionMinimumDominatingSet to MinimumSumMulticenter.
16#[derive(Debug, Clone)]
17pub struct ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
18    target: Decision<MinimumSumMulticenter<SimpleGraph, i64>>,
19    source_num_vertices: usize,
20}
21
22impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
23    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
24    type Target = Decision<MinimumSumMulticenter<SimpleGraph, i64>>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_witness(
35            self.target_problem(),
36            target_solution,
37            |value| value.0,
38            "target placement does not certify a dominating set within the source bound",
39        )?;
40        // Original vertices precede the auxiliary isolated vertices.
41        Ok(target_solution[..self.source_num_vertices].to_vec())
42    }
43}
44
45#[crate::aggregate_reduction(identity)]
46impl crate::rules::AggregateReductionResult
47    for ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter
48{
49}
50
51#[reduction(
52    transform = upper_bound { num_vertices = "num_vertices + 2", num_edges = "num_edges" }
53)]
54impl ReduceTo<Decision<MinimumSumMulticenter<SimpleGraph, i64>>>
55    for Decision<MinimumDominatingSet<SimpleGraph, One>>
56{
57    type Result = ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let source_graph = self.inner().graph();
61        let n = source_graph.num_vertices();
62        let (target_n, centers, threshold) = multicenter_parameters(n, *self.bound())?;
63        let target = MinimumSumMulticenter::new(
64            SimpleGraph::new(target_n, source_graph.edges()),
65            vec![1i64; target_n],
66            vec![1i64; source_graph.num_edges()],
67            centers,
68        );
69        Ok(
70            ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
71                target: Decision::new(target, threshold),
72                source_num_vertices: n,
73            },
74        )
75    }
76}
77
78/// Compute the construction's counts without allocating the graph, so numeric
79/// domain boundaries can be checked independently of available memory.
80fn multicenter_parameters(
81    n: usize,
82    bound: i64,
83) -> Result<(usize, usize, i64), crate::rules::ReductionError> {
84    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
85    type Target = Decision<MinimumSumMulticenter<SimpleGraph, i64>>;
86    let overflow = || {
87        crate::rules::ReductionError::integer_overflow::<Source, Target>(
88            "encoding multicenter construction parameters",
89        )
90    };
91    let extra_vertices = if bound < 0 { 2 } else { 1 };
92    let target_n = n.checked_add(extra_vertices).ok_or_else(overflow)?;
93    let n_i64 = i64::try_from(n).map_err(|_| overflow())?;
94    if bound < 0 {
95        // Two auxiliary isolates cannot both be served by one center.
96        return Ok((target_n, 1, -1));
97    }
98    // No subset contains more than n vertices, so these bounds are equivalent.
99    let q = bound.min(n_i64);
100    let q_usize = usize::try_from(q).map_err(|_| overflow())?;
101    // q <= n and n + 1 was checked above, so q + 1 cannot overflow.
102    Ok((target_n, q_usize + 1, n_i64 - q))
103}
104
105#[cfg(feature = "example-db")]
106pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
107    use crate::export::SolutionPair;
108
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "decisionminimumdominatingset_to_minimumsummulticenter",
111        build: || {
112            crate::example_db::specs::rule_example_with_witness::<
113                _,
114                Decision<MinimumSumMulticenter<SimpleGraph, i64>>,
115            >(
116                Decision::new(
117                    MinimumDominatingSet::new(
118                        SimpleGraph::new(
119                            6,
120                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
121                        ),
122                        vec![One; 6],
123                    ),
124                    2,
125                ),
126                SolutionPair {
127                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
128                    target_config: serde_json::json!(vec![
129                        true, false, false, true, false, false, true
130                    ]),
131                },
132            )
133        },
134    }]
135}
136
137#[cfg(test)]
138#[path = "../unit_tests/rules/decisionminimumdominatingset_minimumsummulticenter.rs"]
139mod tests;
problemreductions/rules/decisionminimumdominatingset_minimumsummulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minimumsummulticenter.rs
