3
$\begingroup$

Is there a way to get Mathematica to compute the domination number (size of the smallest dominating set) of a graph? There doesn't seem to be a direct command for this, so I'm not sure if there would be a clever way to define a command that will do this.

$\endgroup$
  • 1
    $\begingroup$ Hi ! Code requests are usually discouraged around these parts. At least show some effort :) $\endgroup$ – Sektor Nov 10 '14 at 19:13
  • 2
    $\begingroup$ It is NP-Hard. I doubt an exact algorithm will ever be implemented in Mma. $\endgroup$ – Dr. belisarius Nov 10 '14 at 19:53
  • 1
    $\begingroup$ @belisarius I don't think that's a good argument. There are many functions solving NP-hard problems implemented. $\endgroup$ – Juho Mar 18 '15 at 10:40
3
$\begingroup$

First, observe a maximal independent set (note the term maximal, not maximum) is also a dominating set in a graph. A maximal independent set of a graph is equivalent to a maximal clique of its complement. This suggests a straightforward algorithm:

MinimumDominatingSet[g_] := 
  First@MinimalBy[FindClique[GraphComplement[g], Infinity, All], Length];

(This approach only gives an upper bound to the minimum dominating set, since it only gives a minimum independent dominating set. The minimum dominating set is not necessarily independent.)

In a complete graph, the dominating number is one:

g = CompleteGraph[4, VertexLabels -> "Name"];
HighlightGraph[g, MinimumDominatingSet[g]]

You can test this on e.g. small random graphs as well:

g = RandomGraph[{6, 9}, VertexLabels -> "Name"];
HighlightGraph[g, MinimumDominatingSet[g]]

In addition, this is actually much faster than naive brute force:

DominatingSetQ[g_, s_] :=
   !MemberQ[Intersection[s, AdjacencyList[g, #]] & /@ 
     Complement[VertexList[g], s], {}];

Brute[g_] := Module[{sets = Subsets[VertexList[g]]},
   SelectFirst[sets, DominatingSetQ[g, #] &]];

g = CirculantGraph[17, 5, VertexLabels -> "Name"];
Timing[Brute[g]] (* {18.236517, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}} *)
Timing[MinimumDominatingSet[g]] (* {0., {6, 7, 8, 9, 10, 16, 17, 18, 19, 20}} *)
$\endgroup$
2
$\begingroup$

You could try to phrase it as an integer programming problem:

g = HypercubeGraph[5]

(* var[vertex] is 1 if vertex is in the dominating set, 0 otherwise *)
dominatingSet = Map[First]@Keys@Select[
    Association@Last@FindMinimum[
       {Total[var /@ VertexList[g]], (* minimize set size *)
        { KeyValueMap[1 - var[#1] <= Total[var /@ #2] &, IGAdjacencyList[g]], (* every vertex not in the dominating set must have at least one neighbour in the dominating set *)
          1 >= var[#] >= 0 && Element[var[#], Integers] & /@ VertexList[g] }
        },
       var /@ VertexList[g]
       ],
    # > 0 &
    ]

(* {2, 3, 12, 13, 24, 25, 29} *)

HighlightGraph[g, dominatingSet]

enter image description here

$\endgroup$
1
$\begingroup$

A brute force method for the independent domination number is given by...

BF = ButterflyGraph[1]; 
Min[Map[Length, FindIndependentVertexSet[BF, Infinity, All], 2]] 

However, this should only be used for very small graphs. This code simply lists all the maximum independent sets of vertices then maps the length function onto the inner list followed by finding the elements with the smallest cardinality/length in the inner list. Note, this is actually a list of lists (i.e. {{1,3},{2,4}}). I'm sure there is a more efficient way to do this but since it's NP-Hard it can't be used for large graphs anyway.

An easier way is to do the following...

BF = ButterflyGraph[2];
FindIndependentVertexSet[BF, Infinity, All]

Then, just count the number of elements in the last entry since the the list is ordered w.r.t the length function. Since the output is always in abbreviated form this always works. For BF[2], the output is

{{1, 3, 4, 6, 7, 9, 10, 12}, {3, 4, 6, 8, 10}, {2, 4, 9, 10, 12}, {1, 
  5, 7, 9, 12}, {1, 3, 6, 7, 11}, {3, 6, 8, 11}, {2, 5, 9, 12}, {2, 5,
   8, 11}, {2, 4, 8, 10}, {1, 5, 7, 11}}

So here i(BF(2))=4 and $\alpha (BF(2)$ = 8.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.