search

szhorvat / IGraphM

IGraph/M is the igraph interface for Mathematica
http://szhorvat.net/mathematica/IGraphM
Other
90 stars 17 forks source link

Add utility functions for checking whether a vertex subset is dominating #105

Open jplauri opened 4 years ago

jplauri commented 4 years ago

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?

szhorvat commented 4 years ago

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.