IGraphM icon indicating copy to clipboard operation
IGraphM copied to clipboard

Add utility functions for checking whether a vertex subset is dominating

Open jplauri opened this issue 5 years ago • 1 comments

Domination is one of the most central concepts in (algorithmic) graph theory, but there's not a lot of support for domination in IGraphM. As a start, to extend the family consisting of IGDominatorTree and IGImmediateDominators, I'd suggest adding utility functions to verify whether a given subset of vertices form a dominating set.

To check if S is a dominating set in G, we can check if S intersects the neighborhood of each vertex not in S. In Mathematica, one could write this as:

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

It also not at all common to be interested in connected dominating sets, for which a similar check could then by constructed as:

ConnectedDominatingSetQ[g_, s_] := 
  ConnectedGraphQ[Subgraph[g, s]] && DominatingSetQ[g, s];

Ultimately, I think it would be great if IGraphM also had functionality to find a minimum (connected) dominating set, the (connected) domination number and so on, but I think this should be a fine addition and a good start. At the very least, it makes it very easy for the user to write a brute-force algorithm for either problem applicable for tiny graphs.

Do you think adding these functions would make sense?

jplauri avatar May 03 '20 10:05 jplauri

These are all good suggestions. Thanks! I'll also make a few changes to make it easier to get started with development, and will send you an email during next week.

szhorvat avatar May 03 '20 19:05 szhorvat