Minimum Dominating Set

import networkx as nx
import pyomo.core as pyo


def mds(graph: nx.Graph) -> pyo.ConcreteModel:
    model = pyo.ConcreteModel()
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)

    @model.Constraint(graph.nodes)
    def dominating_rule(model, idx):
        sum_of_neighbors = sum(model.x[neighbor] for neighbor in graph.neighbors(idx))
        return model.x[idx] + sum_of_neighbors >= 1

    model.cost = pyo.Objective(expr=sum(model.x.values()), sense=pyo.minimize)

    return model

This function generates a PYOMO model which formulates the Minimum Dominating Set problem. The problem concerns finding the smallest set of vertices in a graph such that every vertex in the graph is adjacent to at least one member of the set. The model consists of:

  • Index set declarations (model.Nodes, model.Arcs).
  • Binary variable declaration for each node (model.x) indicating whether that node is chosen to be included in the set.
  • Constraint rule - for each node, it must be a part of the chosen set or be neighbored by one.
  • Objective rule – the sum of the variables equals to the set size.