I believe Minimum Dominating Set (MDS) is NP-hard for bounded degeneracy and their subset bounded degree graphs, but a paper appear to suggest tractability. Enumeration of Minimal Dominating Sets and Variants p.5

Proposition 1. Dom admits a polynomial delay algorithm when restricted to

  1. Strongly chordal graphs.

  2. Graph classes of bounded degeneracy.

The delay of the algorithm is the time between enumerating two MDSs after polynomial preprocessing (unless I have misunderstood the definitions on p. 3). According to graphclasses.org MDS is linear for strongly chordal graphs.

Does the paper imply $\exp(o(n))$ complexity of MDS for graphs of bounded degeneracy (and bounded degree)?


No it does not. The problem DOM considered by the paper seems to be the enumeration of minimal, not minimum dominating sets. Usually minimal means a solution $X$ such that there is no other solution $X'$ with $X' \subsetneq X$. The solution $X$ is not necessarily the minimum size. While minimal dominating sets can be enumerated with polynomial delay in bounded degeneracy graphs, there seems to be no guarantees that this enumeration finds the minimum dominating set before enumerating an exponential number of dominating sets that are minimal, but not minimum.

  • $\begingroup$ Indeed, thank you. $\endgroup$ – joro Jan 15 '20 at 15:56

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.