problemreductions/models/graph/

minimum_dominating_set.rs

//! Dominating Set problem implementation.
//!
//! The Dominating Set problem asks for a minimum weight subset of vertices
//! such that every vertex is either in the set or adjacent to a vertex in the set.

use crate::models::decision::Decision;
use crate::registry::{CreateSpec, FieldInfo, ProblemSchemaEntry, VariantDimension};
use crate::topology::{Graph, SimpleGraph};
use crate::traits::Problem;
use crate::types::{Min, One, WeightElement};
use num_traits::Zero;
use serde::{Deserialize, Serialize};
use std::collections::HashSet;

inventory::submit! {
    ProblemSchemaEntry {
        name: "MinimumDominatingSet",
        display_name: "Minimum Dominating Set",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
            VariantDimension::new("weight", "i64", &["i64", "One"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Find minimum weight dominating set in a graph",
        fields: MinimumDominatingSetCreateSpec::<i64>::FIELDS,
    }
}

/// The Dominating Set problem.
///
/// Given a graph G = (V, E) and weights w_v for each vertex,
/// find a subset D ⊆ V such that:
/// - Every vertex is either in D or adjacent to a vertex in D (domination)
/// - The total weight Σ_{v ∈ D} w_v is minimized
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::MinimumDominatingSet;
/// use problemreductions::topology::SimpleGraph;
/// use problemreductions::{Problem, BruteForce};
///
/// // Star graph: center dominates all
/// let graph = SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]);
/// let problem = MinimumDominatingSet::new(graph, vec![1; 4]);
///
/// let solver = BruteForce::new();
/// let solutions = solver.find_all_witnesses(&problem).unwrap();
///
/// // Minimum dominating set is just the center vertex
/// assert!(solutions.contains(&vec![true, false, false, false]));
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "MinimumDominatingSetData<G, W>")]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
pub struct MinimumDominatingSet<G, W> {
    /// The underlying graph.
    graph: G,
    /// Weights for each vertex.
    weights: Vec<W>,
}

#[derive(Deserialize)]
struct MinimumDominatingSetData<G, W> {
    graph: G,
    weights: Vec<W>,
}

impl<G, W> TryFrom<MinimumDominatingSetData<G, W>> for MinimumDominatingSet<G, W>
where
    G: Graph,
    W: Clone + Default,
{
    type Error = crate::registry::ConstructionError;

    fn try_from(data: MinimumDominatingSetData<G, W>) -> Result<Self, Self::Error> {
        Self::try_new(data.graph, data.weights)
    }
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct MinimumDominatingSetCreateSpec<W> {
    /// The underlying graph G=(V,E).
    graph: SimpleGraph,
    /// Vertex weights w: V -> R.
    weights: Vec<W>,
}

impl<W: Clone + Default> TryFrom<MinimumDominatingSetCreateSpec<W>>
    for MinimumDominatingSet<SimpleGraph, W>
{
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: MinimumDominatingSetCreateSpec<W>) -> Result<Self, Self::Error> {
        Self::try_new(spec.graph, spec.weights)
    }
}

impl<G: Graph, W: Clone + Default> MinimumDominatingSet<G, W> {
    /// Create a Dominating Set problem from a graph with given weights.
    pub fn new(graph: G, weights: Vec<W>) -> Self {
        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(graph: G, weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
        if weights.len() != graph.num_vertices() {
            return Err(crate::registry::ConstructionError::length_mismatch(
                "weights",
                weights.len(),
                graph.num_vertices(),
            ));
        }
        Ok(Self { graph, weights })
    }

    /// Get a reference to the underlying graph.
    pub fn graph(&self) -> &G {
        &self.graph
    }

    /// Get neighbors of a vertex.
    pub fn neighbors(&self, v: usize) -> Vec<usize> {
        self.graph.neighbors(v)
    }

    /// Get the closed neighborhood `N[v] = {v} ∪ N(v)`.
    pub fn closed_neighborhood(&self, v: usize) -> HashSet<usize> {
        let mut neighborhood: HashSet<usize> = self.neighbors(v).into_iter().collect();
        neighborhood.insert(v);
        neighborhood
    }

    /// Get a reference to the weights slice.
    pub fn weights(&self) -> &[W] {
        &self.weights
    }

    /// Check if a configuration is a valid dominating set.
    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
        self.is_dominating(config)
    }

    /// Check if a set of vertices is a dominating set.
    fn is_dominating(&self, config: &[bool]) -> bool {
        let n = self.graph.num_vertices();
        let mut dominated = vec![false; n];

        for (v, &selected) in config.iter().enumerate() {
            if selected {
                // v dominates itself
                dominated[v] = true;
                // v dominates all its neighbors
                for neighbor in self.neighbors(v) {
                    if neighbor < n {
                        dominated[neighbor] = true;
                    }
                }
            }
        }

        dominated.iter().all(|&d| d)
    }
}

impl<G: Graph, W: WeightElement> MinimumDominatingSet<G, W> {
    /// Get the number of vertices in the underlying graph.
    pub fn num_vertices(&self) -> usize {
        self.graph().num_vertices()
    }

    /// Get the number of edges in the underlying graph.
    pub fn num_edges(&self) -> usize {
        self.graph().num_edges()
    }
}

impl<G, W> Problem for MinimumDominatingSet<G, W>
where
    G: Graph + crate::variant::VariantParam,
    W: WeightElement + crate::variant::VariantParam,
{
    const NAME: &'static str = "MinimumDominatingSet";
    type Solution = Vec<bool>;
    type Value = Min<W::Sum>;

    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![G, W]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
        if config.len() != self.graph.num_vertices() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "vertex-selection length does not match the graph".into(),
            ));
        }
        Ok({
            if !self.is_dominating(config) {
                return Ok(Min(None));
            }
            let mut total = W::Sum::zero();
            for (i, &selected) in config.iter().enumerate() {
                if selected {
                    total = W::checked_add_to_sum(
                        total,
                        self.weights[i].to_sum(),
                        "summing selected dominating-set weights",
                    )?;
                }
            }
            Min(Some(total))
        })
    }
}

impl<G, W> crate::solvers::BruteForceProblem for MinimumDominatingSet<G, W>
where
    G: Graph + crate::variant::VariantParam,
    W: WeightElement + crate::variant::VariantParam,
{
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.graph.num_vertices()]
    }
}

crate::impl_random_generate!(MinimumDominatingSet<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
    Ok(MinimumDominatingSet::new(spec.graph()?, vec![1; spec.num_vertices]))
});
crate::impl_random_generate!(MinimumDominatingSet<SimpleGraph, One>, crate::random::SimpleGraphRandomSpec, |spec| {
    Ok(MinimumDominatingSet::new(spec.graph()?, vec![One; spec.num_vertices]))
});

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct MinimumDominatingSetOneCreateSpec {
    /// The underlying graph.
    graph: SimpleGraph,
}

impl TryFrom<MinimumDominatingSetOneCreateSpec> for MinimumDominatingSet<SimpleGraph, One> {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: MinimumDominatingSetOneCreateSpec) -> Result<Self, Self::Error> {
        let weights = vec![One; spec.graph.num_vertices()];
        Self::try_new(spec.graph, weights)
    }
}

crate::declare_variants! {
    default MinimumDominatingSet<SimpleGraph, i64> => "1.4969^num_vertices" create MinimumDominatingSetCreateSpec<i64> random,
    MinimumDominatingSet<SimpleGraph, One> => "1.4969^num_vertices" create MinimumDominatingSetOneCreateSpec random,
}

crate::register_brute_force! {
    MinimumDominatingSet<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
    MinimumDominatingSet<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

impl<G, W> crate::models::decision::DecisionProblemMeta for MinimumDominatingSet<G, W>
where
    G: Graph + crate::variant::VariantParam,
    W: WeightElement + crate::variant::VariantParam,
    W::Sum: std::fmt::Debug + serde::Serialize + serde::de::DeserializeOwned,
{
    const DECISION_NAME: &'static str = "DecisionMinimumDominatingSet";
}

impl Decision<MinimumDominatingSet<SimpleGraph, i64>> {
    /// Number of vertices in the underlying graph.
    pub fn num_vertices(&self) -> usize {
        self.inner().num_vertices()
    }

    /// Number of edges in the underlying graph.
    pub fn num_edges(&self) -> usize {
        self.inner().num_edges()
    }

    /// Decision bound as a nonnegative integer.
    pub fn k(&self) -> usize {
        (*self.bound()).try_into().unwrap_or(0)
    }
}

impl Decision<MinimumDominatingSet<SimpleGraph, One>> {
    /// Number of vertices in the underlying graph.
    pub fn num_vertices(&self) -> usize {
        self.inner().num_vertices()
    }

    /// Number of edges in the underlying graph.
    pub fn num_edges(&self) -> usize {
        self.inner().num_edges()
    }

    /// Decision bound as a nonnegative integer.
    pub fn k(&self) -> usize {
        (*self.bound()).try_into().unwrap_or(0)
    }
}

crate::register_decision_variant!(
    MinimumDominatingSet<SimpleGraph, i64>,
    "DecisionMinimumDominatingSet",
    "1.4969^num_vertices",
    &[],
    "Decision version: does a dominating set of cost <= bound exist?",
    category: crate::registry::ProblemCategory::Graph,
    dims: [
        VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
        VariantDimension::new("weight", "i64", &["i64", "One"]),
    ],
    fields: [
        FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
        FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
        FieldInfo { name: "bound", type_name: "i64", description: "Decision bound (maximum allowed dominating-set cost)" },
    ],
    additional: [MinimumDominatingSet<SimpleGraph, One> => "1.4969^num_vertices"],
    decode: |_, indices: Vec<usize>| crate::config::config_to_bits(&indices)
);

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "minimum_dominating_set_simplegraph",
        instance: Box::new(MinimumDominatingSet::new(
            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
            vec![1i64; 5],
        )),
        optimal_config: serde_json::json!(vec![false, false, true, true, false]),
        optimal_value: serde_json::json!(2),
    }]
}

#[cfg(feature = "example-db")]
pub(crate) fn decision_canonical_model_example_specs(
) -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![
        crate::example_db::specs::ModelExampleSpec {
            id: "decision_minimum_dominating_set_simplegraph",
            instance: Box::new(Decision::new(
                MinimumDominatingSet::new(
                    SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
                    vec![1i64; 5],
                ),
                2,
            )),
            optimal_config: serde_json::json!(vec![false, false, true, true, false]),
            optimal_value: serde_json::json!(true),
        },
        crate::example_db::specs::ModelExampleSpec {
            id: "decision_minimum_dominating_set_six_vertex_graph",
            instance: Box::new(Decision::new(
                MinimumDominatingSet::new(
                    SimpleGraph::new(
                        6,
                        vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
                    ),
                    vec![One; 6],
                ),
                2,
            )),
            optimal_config: serde_json::json!(vec![true, false, false, true, false, false]),
            optimal_value: serde_json::json!(true),
        },
    ]
}

#[cfg(feature = "example-db")]
pub(crate) fn decision_canonical_rule_example_specs(
) -> Vec<crate::example_db::specs::RuleExampleSpec> {
    vec![
        crate::example_db::specs::RuleExampleSpec {
            id: "decision_minimum_dominating_set_to_minimum_dominating_set",
            build: || {
                use crate::example_db::specs::assemble_rule_example;
                use crate::export::SolutionPair;
                use crate::rules::{AggregateReductionResult, ReduceToAggregate};

                let source = crate::models::decision::Decision::new(
                    MinimumDominatingSet::new(
                        SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
                        vec![1i64; 5],
                    ),
                    2,
                );
                let result = source
                    .reduce_to_aggregate()
                    .expect("reduction should succeed");
                let target = result.target_problem();
                let config = vec![false, false, true, true, false];
                assemble_rule_example(
                    &source,
                    target,
                    vec![SolutionPair {
                        source_config: serde_json::json!(config.clone()),
                        target_config: serde_json::json!(config),
                    }],
                )
            },
        },
        // Cardinality variant: Decision<MDS<SG, One>> → MDS<SG, One> (aggregate)
        crate::example_db::specs::RuleExampleSpec {
            id: "decision_cardinality_dominating_set_to_minimum_dominating_set",
            build: || {
                use crate::example_db::specs::assemble_rule_example;
                use crate::export::SolutionPair;
                use crate::rules::{AggregateReductionResult, ReduceToAggregate};

                let source = crate::models::decision::Decision::new(
                    MinimumDominatingSet::new(
                        SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
                        vec![One; 5],
                    ),
                    2,
                );
                let result = source
                    .reduce_to_aggregate()
                    .expect("reduction should succeed");
                let target = result.target_problem();
                let config = vec![false, false, true, true, false];
                assemble_rule_example(
                    &source,
                    target,
                    vec![SolutionPair {
                        source_config: serde_json::json!(config.clone()),
                        target_config: serde_json::json!(config),
                    }],
                )
            },
        },
    ]
}

/// Check if a set of vertices is a dominating set.
///
/// # Panics
/// Panics if `selected.len() != graph.num_vertices()`.
#[cfg(test)]
pub(crate) fn is_dominating_set<G: Graph>(graph: &G, selected: &[bool]) -> bool {
    assert_eq!(
        selected.len(),
        graph.num_vertices(),
        "selected length must match num_vertices"
    );

    // Check each vertex is dominated
    for v in 0..graph.num_vertices() {
        if selected[v] {
            continue; // v dominates itself
        }
        // Check if any neighbor of v is selected
        if !graph.neighbors(v).iter().any(|&u| selected[u]) {
            return false;
        }
    }

    true
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/minimum_dominating_set.rs"]
mod tests;