Skip to content

Minimum Dominating Set Example

Download Notebook

The Minimum Dominating Set problem finds a smallest set of nodes such that every node in the graph is either in the set or adjacent to a node in the set. It is NP-hard and has applications in wireless network design, facility placement, and social network influence.

import getpass
import os

import networkx as nx
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.minimum_dominating_set import (
    MdsCollection,
    MdsData,
    MdsFormulation,
    MdsInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Build a graph from a NetworkX graph using the from_graph factory. Here we use a 6-node path graph.

graph = nx.path_graph(6)
data = MdsData.from_graph(graph)
print(data.to_string())

Minimum Dominating Set Data:
  Nodes: 6
  Edges: 5

Plot Data

Visualize the graph structure.

data.plot()


<Axes: title={'center': 'Minimum Dominating Set — 6 nodes, 5 edges'}>
png

Create Formulation

Minimize the number of selected nodes such that every node is dominated.

formulation = MdsFormulation()
print(formulation.to_string(data))

Minimum Dominating Set Formulation:
  Nodes: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 5
  x[i] = 1 if node i is in the dominating set
  Total: 6 binary variables

Objective:
  minimize sum_i x[i]

Constraints:
  1. Domination (6 constraints):
     x[i] + sum_{j in N(i)} x[j] >= 1  for each node i

Create Instance

Combine data and formulation into a solvable instance.

instance = MdsInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Minimum Dominating Set Data:
  Nodes: 6
  Edges: 5
Formulation:Minimum Dominating Set Formulation:
  Nodes: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 5
  x[i] = 1 if node i is in the dominating set
  Total: 6 binary variables

Objective:
  minimize sum_i x[i]

Constraints:
  1. Domination (6 constraints):
     x[i] + sum_{j in N(i)} x[j] >= 1  for each node i

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

Waiting for result | elapsed 0:00:00 | poll 1 | next check in 0.5s

Waiting for result | elapsed 0:00:01 | poll 2 | next check in 1s

Waiting for result | elapsed 0:00:03 | poll 3 | next check in 2s

Waiting for result | elapsed 0:00:05 | poll 4 | next check in 4s

Waiting for result | elapsed 0:00:10 | poll 5 | next check in 8s

Waiting for result | elapsed 0:00:18 | poll 6 | next check in 16s

2026-08-20 11:54:28 INFO     Solve job '46d04e11-2bad-4897-bcf4-6d0f06c6ffbf' finished with status 'DONE' after    
                             0:00:35.                                                                              

Minimum Dominating Set Solution:
  Set size: 2
  Valid: True
  Dominating set: [1, 4]

Plot Solution

Visualize the optimal dominating set.

uc_solution.plot(data)


<Axes: title={'center': 'Minimum Dominating Set — size=2, valid=True'}>
png

Collections

Generate a benchmark collection of random instances for batch processing.

collection = MdsCollection.from_random(min_nodes=4, max_nodes=6, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: minimum_dominating_set<s42_n4_i0>
Minimize
  x_0 + x_1 + x_2 + x_3
Subject To
  dominate_0: x_0 + x_1 + x_2 + x_3 >= 1
  dominate_1: x_0 + x_1 >= 1
  dominate_2: x_0 + x_2 + x_3 >= 1
  dominate_3: x_0 + x_2 + x_3 >= 1
Binary
  x_0 x_1 x_2 x_3