problemreductions/models/graph/
minimum_dominating_set.rs

1//! Dominating Set problem implementation.
2//!
3//! The Dominating Set problem asks for a minimum weight subset of vertices
4//! such that every vertex is either in the set or adjacent to a vertex in the set.
5
6use crate::models::decision::Decision;
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::{Min, One, WeightElement};
11use num_traits::Zero;
12use serde::{Deserialize, Serialize};
13use std::collections::HashSet;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "MinimumDominatingSet",
18        display_name: "Minimum Dominating Set",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22            VariantDimension::new("weight", "i32", &["i32", "One"]),
23        ],
24        module_path: module_path!(),
25        description: "Find minimum weight dominating set in a graph",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
28            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
29        ],
30    }
31}
32
33/// The Dominating Set problem.
34///
35/// Given a graph G = (V, E) and weights w_v for each vertex,
36/// find a subset D ⊆ V such that:
37/// - Every vertex is either in D or adjacent to a vertex in D (domination)
38/// - The total weight Σ_{v ∈ D} w_v is minimized
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::MinimumDominatingSet;
44/// use problemreductions::topology::SimpleGraph;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// // Star graph: center dominates all
48/// let graph = SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]);
49/// let problem = MinimumDominatingSet::new(graph, vec![1; 4]);
50///
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_witnesses(&problem);
53///
54/// // Minimum dominating set is just the center vertex
55/// assert!(solutions.contains(&vec![1, 0, 0, 0]));
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct MinimumDominatingSet<G, W> {
59    /// The underlying graph.
60    graph: G,
61    /// Weights for each vertex.
62    weights: Vec<W>,
63}
64
65impl<G: Graph, W: Clone + Default> MinimumDominatingSet<G, W> {
66    /// Create a Dominating Set problem from a graph with given weights.
67    pub fn new(graph: G, weights: Vec<W>) -> Self {
68        assert_eq!(
69            weights.len(),
70            graph.num_vertices(),
71            "weights length must match graph num_vertices"
72        );
73        Self { graph, weights }
74    }
75
76    /// Get a reference to the underlying graph.
77    pub fn graph(&self) -> &G {
78        &self.graph
79    }
80
81    /// Get neighbors of a vertex.
82    pub fn neighbors(&self, v: usize) -> Vec<usize> {
83        self.graph.neighbors(v)
84    }
85
86    /// Get the closed neighborhood `N[v] = {v} ∪ N(v)`.
87    pub fn closed_neighborhood(&self, v: usize) -> HashSet<usize> {
88        let mut neighborhood: HashSet<usize> = self.neighbors(v).into_iter().collect();
89        neighborhood.insert(v);
90        neighborhood
91    }
92
93    /// Get a reference to the weights slice.
94    pub fn weights(&self) -> &[W] {
95        &self.weights
96    }
97
98    /// Check if a configuration is a valid dominating set.
99    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
100        self.is_dominating(config)
101    }
102
103    /// Check if a set of vertices is a dominating set.
104    fn is_dominating(&self, config: &[usize]) -> bool {
105        let n = self.graph.num_vertices();
106        let mut dominated = vec![false; n];
107
108        for (v, &selected) in config.iter().enumerate() {
109            if selected == 1 {
110                // v dominates itself
111                dominated[v] = true;
112                // v dominates all its neighbors
113                for neighbor in self.neighbors(v) {
114                    if neighbor < n {
115                        dominated[neighbor] = true;
116                    }
117                }
118            }
119        }
120
121        dominated.iter().all(|&d| d)
122    }
123}
124
125impl<G: Graph, W: WeightElement> MinimumDominatingSet<G, W> {
126    /// Get the number of vertices in the underlying graph.
127    pub fn num_vertices(&self) -> usize {
128        self.graph().num_vertices()
129    }
130
131    /// Get the number of edges in the underlying graph.
132    pub fn num_edges(&self) -> usize {
133        self.graph().num_edges()
134    }
135}
136
137impl<G, W> Problem for MinimumDominatingSet<G, W>
138where
139    G: Graph + crate::variant::VariantParam,
140    W: WeightElement + crate::variant::VariantParam,
141{
142    const NAME: &'static str = "MinimumDominatingSet";
143    type Value = Min<W::Sum>;
144
145    fn variant() -> Vec<(&'static str, &'static str)> {
146        crate::variant_params![G, W]
147    }
148
149    fn dims(&self) -> Vec<usize> {
150        vec![2; self.graph.num_vertices()]
151    }
152
153    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
154        if !self.is_dominating(config) {
155            return Min(None);
156        }
157        let mut total = W::Sum::zero();
158        for (i, &selected) in config.iter().enumerate() {
159            if selected == 1 {
160                total += self.weights[i].to_sum();
161            }
162        }
163        Min(Some(total))
164    }
165}
166
167crate::declare_variants! {
168    default MinimumDominatingSet<SimpleGraph, i32> => "1.4969^num_vertices",
169    MinimumDominatingSet<SimpleGraph, One> => "1.4969^num_vertices",
170}
171
172impl<G, W> crate::models::decision::DecisionProblemMeta for MinimumDominatingSet<G, W>
173where
174    G: Graph + crate::variant::VariantParam,
175    W: WeightElement + crate::variant::VariantParam,
176    W::Sum: std::fmt::Debug + serde::Serialize + serde::de::DeserializeOwned,
177{
178    const DECISION_NAME: &'static str = "DecisionMinimumDominatingSet";
179}
180
181impl Decision<MinimumDominatingSet<SimpleGraph, i32>> {
182    /// Number of vertices in the underlying graph.
183    pub fn num_vertices(&self) -> usize {
184        self.inner().num_vertices()
185    }
186
187    /// Number of edges in the underlying graph.
188    pub fn num_edges(&self) -> usize {
189        self.inner().num_edges()
190    }
191
192    /// Decision bound as a nonnegative integer.
193    pub fn k(&self) -> usize {
194        (*self.bound()).try_into().unwrap_or(0)
195    }
196}
197
198impl Decision<MinimumDominatingSet<SimpleGraph, One>> {
199    /// Number of vertices in the underlying graph.
200    pub fn num_vertices(&self) -> usize {
201        self.inner().num_vertices()
202    }
203
204    /// Number of edges in the underlying graph.
205    pub fn num_edges(&self) -> usize {
206        self.inner().num_edges()
207    }
208
209    /// Decision bound as a nonnegative integer.
210    pub fn k(&self) -> usize {
211        (*self.bound()).try_into().unwrap_or(0)
212    }
213}
214
215crate::register_decision_variant!(
216    MinimumDominatingSet<SimpleGraph, i32>,
217    "DecisionMinimumDominatingSet",
218    "1.4969^num_vertices",
219    &[],
220    "Decision version: does a dominating set of cost <= bound exist?",
221    dims: [
222        VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
223        VariantDimension::new("weight", "i32", &["i32", "One"]),
224    ],
225    fields: [
226        FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
227        FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
228        FieldInfo { name: "bound", type_name: "i32", description: "Decision bound (maximum allowed dominating-set cost)" },
229    ],
230    size_getters: [("num_vertices", num_vertices), ("num_edges", num_edges)]
231);
232
233impl crate::traits::DeclaredVariant for Decision<MinimumDominatingSet<SimpleGraph, One>> {}
234
235inventory::submit! {
236    crate::registry::VariantEntry {
237        name: <Decision<MinimumDominatingSet<SimpleGraph, One>> as Problem>::NAME,
238        variant_fn: <Decision<MinimumDominatingSet<SimpleGraph, One>> as Problem>::variant,
239        complexity: "1.4969^num_vertices",
240        complexity_eval_fn: |any| {
241            let problem = any
242                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
243                .expect("DecisionMinimumDominatingSet complexity source type mismatch");
244            1.4969_f64.powf(problem.num_vertices() as f64)
245        },
246        is_default: false,
247        aliases: &[],
248        factory: |data| {
249            serde_json::from_value::<Decision<MinimumDominatingSet<SimpleGraph, One>>>(data)
250                .map(|problem| Box::new(problem) as Box<dyn crate::registry::DynProblem>)
251        },
252        serialize_fn: |any| {
253            any.downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
254                .and_then(|problem| serde_json::to_value(problem).ok())
255        },
256        solve_value_fn: |any| {
257            let problem = any
258                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
259                .expect("DecisionMinimumDominatingSet value solve source type mismatch");
260            let (value, _) = crate::solvers::BruteForce::new().solve_with_witnesses(problem);
261            crate::registry::format_metric(&value)
262        },
263        solve_witness_fn: |any| {
264            let problem = any
265                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
266                .expect("DecisionMinimumDominatingSet witness solve source type mismatch");
267            let (value, witnesses) = crate::solvers::BruteForce::new().solve_with_witnesses(problem);
268            witnesses
269                .into_iter()
270                .next()
271                .map(|config| (config, crate::registry::format_metric(&value)))
272        },
273    }
274}
275
276// Decision<MDS<SG, One>> → MDS<SG, One>: both witness (identity config) and aggregate (solve + compare)
277inventory::submit! {
278    crate::rules::ReductionEntry {
279        source_name: "DecisionMinimumDominatingSet",
280        target_name: "MinimumDominatingSet",
281        source_variant_fn: <Decision<MinimumDominatingSet<SimpleGraph, One>> as Problem>::variant,
282        target_variant_fn: <MinimumDominatingSet<SimpleGraph, One> as Problem>::variant,
283        overhead_fn: || crate::rules::ReductionOverhead::identity(&["num_vertices", "num_edges"]),
284        module_path: module_path!(),
285        reduce_fn: Some(|any| {
286            let source = any
287                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
288                .expect("DecisionMinimumDominatingSet witness reduction source type mismatch");
289            Box::new(
290                <Decision<MinimumDominatingSet<SimpleGraph, One>> as crate::rules::ReduceTo<
291                    MinimumDominatingSet<SimpleGraph, One>,
292                >>::reduce_to(source),
293            )
294        }),
295        reduce_aggregate_fn: Some(|any| {
296            let source = any
297                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
298                .expect("DecisionMinimumDominatingSet aggregate reduction source type mismatch");
299            Box::new(
300                <Decision<MinimumDominatingSet<SimpleGraph, One>> as crate::rules::ReduceToAggregate<
301                    MinimumDominatingSet<SimpleGraph, One>,
302                >>::reduce_to_aggregate(source),
303            )
304        }),
305        capabilities: crate::rules::EdgeCapabilities::both(),
306        overhead_eval_fn: |any| {
307            let source = any
308                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
309                .expect("DecisionMinimumDominatingSet overhead source type mismatch");
310            crate::types::ProblemSize::new(vec![
311                ("num_vertices", source.num_vertices()),
312                ("num_edges", source.num_edges()),
313            ])
314        },
315        source_size_fn: |any| {
316            let source = any
317                .downcast_ref::<Decision<MinimumDominatingSet<SimpleGraph, One>>>()
318                .expect("DecisionMinimumDominatingSet size source type mismatch");
319            crate::types::ProblemSize::new(vec![
320                ("num_vertices", source.num_vertices()),
321                ("num_edges", source.num_edges()),
322                ("k", source.k()),
323            ])
324        },
325    }
326}
327
328// Reverse edge: MDS<SG, One> → Decision<MDS<SG, One>> (Turing)
329inventory::submit! {
330    crate::rules::ReductionEntry {
331        source_name: "MinimumDominatingSet",
332        target_name: "DecisionMinimumDominatingSet",
333        source_variant_fn: <MinimumDominatingSet<SimpleGraph, One> as Problem>::variant,
334        target_variant_fn: <Decision<MinimumDominatingSet<SimpleGraph, One>> as Problem>::variant,
335        overhead_fn: || crate::rules::ReductionOverhead::identity(&["num_vertices", "num_edges"]),
336        module_path: module_path!(),
337        reduce_fn: None,
338        reduce_aggregate_fn: None,
339        capabilities: crate::rules::EdgeCapabilities::turing(),
340        overhead_eval_fn: |any| {
341            let source = any
342                .downcast_ref::<MinimumDominatingSet<SimpleGraph, One>>()
343                .expect("DecisionMinimumDominatingSet turing overhead source type mismatch");
344            crate::types::ProblemSize::new(vec![
345                ("num_vertices", source.num_vertices()),
346                ("num_edges", source.num_edges()),
347            ])
348        },
349        source_size_fn: |any| {
350            let source = any
351                .downcast_ref::<MinimumDominatingSet<SimpleGraph, One>>()
352                .expect("DecisionMinimumDominatingSet turing size source type mismatch");
353            crate::types::ProblemSize::new(vec![
354                ("num_vertices", source.num_vertices()),
355                ("num_edges", source.num_edges()),
356            ])
357        },
358    }
359}
360
361#[cfg(feature = "example-db")]
362pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
363    vec![crate::example_db::specs::ModelExampleSpec {
364        id: "minimum_dominating_set_simplegraph_i32",
365        instance: Box::new(MinimumDominatingSet::new(
366            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
367            vec![1i32; 5],
368        )),
369        optimal_config: vec![0, 0, 1, 1, 0],
370        optimal_value: serde_json::json!(2),
371    }]
372}
373
374#[cfg(feature = "example-db")]
375pub(crate) fn decision_canonical_model_example_specs(
376) -> Vec<crate::example_db::specs::ModelExampleSpec> {
377    vec![
378        crate::example_db::specs::ModelExampleSpec {
379            id: "decision_minimum_dominating_set_simplegraph_i32",
380            instance: Box::new(Decision::new(
381                MinimumDominatingSet::new(
382                    SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
383                    vec![1i32; 5],
384                ),
385                2,
386            )),
387            optimal_config: vec![0, 0, 1, 1, 0],
388            optimal_value: serde_json::json!(true),
389        },
390        crate::example_db::specs::ModelExampleSpec {
391            id: "decision_minimum_dominating_set_simplegraph_one",
392            instance: Box::new(Decision::new(
393                MinimumDominatingSet::new(
394                    SimpleGraph::new(
395                        6,
396                        vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
397                    ),
398                    vec![One; 6],
399                ),
400                2,
401            )),
402            optimal_config: vec![1, 0, 0, 1, 0, 0],
403            optimal_value: serde_json::json!(true),
404        },
405    ]
406}
407
408#[cfg(feature = "example-db")]
409pub(crate) fn decision_canonical_rule_example_specs(
410) -> Vec<crate::example_db::specs::RuleExampleSpec> {
411    vec![
412        crate::example_db::specs::RuleExampleSpec {
413            id: "decision_minimum_dominating_set_to_minimum_dominating_set",
414            build: || {
415                use crate::example_db::specs::assemble_rule_example;
416                use crate::export::SolutionPair;
417                use crate::rules::{AggregateReductionResult, ReduceToAggregate};
418
419                let source = crate::models::decision::Decision::new(
420                    MinimumDominatingSet::new(
421                        SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
422                        vec![1i32; 5],
423                    ),
424                    2,
425                );
426                let result = source.reduce_to_aggregate();
427                let target = result.target_problem();
428                let config = vec![0, 0, 1, 1, 0];
429                assemble_rule_example(
430                    &source,
431                    target,
432                    vec![SolutionPair {
433                        source_config: config.clone(),
434                        target_config: config,
435                    }],
436                )
437            },
438        },
439        // One-weight variant: Decision<MDS<SG, One>> → MDS<SG, One> (aggregate)
440        crate::example_db::specs::RuleExampleSpec {
441            id: "decision_minimum_dominating_set_one_to_minimum_dominating_set_one",
442            build: || {
443                use crate::example_db::specs::assemble_rule_example;
444                use crate::export::SolutionPair;
445                use crate::rules::{AggregateReductionResult, ReduceToAggregate};
446
447                let source = crate::models::decision::Decision::new(
448                    MinimumDominatingSet::new(
449                        SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
450                        vec![One; 5],
451                    ),
452                    2,
453                );
454                let result = source.reduce_to_aggregate();
455                let target = result.target_problem();
456                let config = vec![0, 0, 1, 1, 0];
457                assemble_rule_example(
458                    &source,
459                    target,
460                    vec![SolutionPair {
461                        source_config: config.clone(),
462                        target_config: config,
463                    }],
464                )
465            },
466        },
467    ]
468}
469
470/// Check if a set of vertices is a dominating set.
471///
472/// # Panics
473/// Panics if `selected.len() != graph.num_vertices()`.
474#[cfg(test)]
475pub(crate) fn is_dominating_set<G: Graph>(graph: &G, selected: &[bool]) -> bool {
476    assert_eq!(
477        selected.len(),
478        graph.num_vertices(),
479        "selected length must match num_vertices"
480    );
481
482    // Check each vertex is dominated
483    for v in 0..graph.num_vertices() {
484        if selected[v] {
485            continue; // v dominates itself
486        }
487        // Check if any neighbor of v is selected
488        if !graph.neighbors(v).iter().any(|&u| selected[u]) {
489            return false;
490        }
491    }
492
493    true
494}
495
496#[cfg(test)]
497#[path = "../../unit_tests/models/graph/minimum_dominating_set.rs"]
498mod tests;
problemreductions/models/graph/minimum_dominating_set.rs

problemreductions/models/graph/
minimum_dominating_set.rs
