# Minimum dominating set
#
# Chooses the fewest vertices such that every vertex is either chosen or
# adjacent to a chosen one. The closed neighbourhood of each vertex comes
# from a parametric set, so the constraint sums over a script-defined index
# domain rather than a literal set.
#
# Technique: Closed-neighbourhood covering using a parametric set function
# N(v) supplied by the script.
#
# On this instance the optimum is 3 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Haynes, T. W., Hedetniemi, S. T. and Slater, P. J. (2013).
# Fundamentals of Domination in Graphs. CRC Press. doi:10.1201/9781482246582
model m
set V = {1, 2, 3, 4}
set N(V) = closedNeighbourhood()
const w = {1, 3, 3, 6}, forall v in V
bin y, forall v in V
min sum_{v in V}{w_{v} * y_{v}}
# each vertex is dominated by something in its closed neighbourhood
constr sum_{u in N(v)}{y_{u}} >= 1, forall v in V
end
import elytica
def closedNeighbourhood():
return {1: [1, 2, 3], 2: [1, 2, 3], 3: [1, 2, 3, 4], 4: [3, 4]}
Read this through MCP: read with path: "formulations/dominating-set", or resource hlpl://formulations/dominating-set.