Several papers appear to imply P=NP via chordal graphs, which suggests something is wrong.

As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$ are the independence domination number.


Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.

According to graphclasses.org

and a paper p. 55 of the document and 65 of the pdf:

In chordal graphs Domination is NP-complete and Independent Domination is polynomial.

The equality in Theorem 1.1 appears to imply P=NP since we can compute $\gamma(G)=i(G)$ in chordal graphs by the above result.

What is wrong with this?


1 Answer 1


The problem is that you confused the definiton in the paper of Aharoni & Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set dominating an independent set, and the latter one is the smallest size of a dominating set which is also an independent set.

These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:


where $\gamma(G)=2$ and $i(G)=3$.

As a comment, Allan & Laskar showed that $\gamma(G)=i(G)$ when $G$ is claw-free, but there are no such conclusions for chordal graphs.

  • $\begingroup$ Thanks, indeed there are counterexamples to gamma(G)=i(G) for chordal. $\endgroup$
    – joro
    Mar 12, 2015 at 11:28
  • $\begingroup$ So, just to be clear, we're saying that Theorem 1.1 in OP's question is wrong, right? @WillardZahn $\endgroup$ Mar 12, 2015 at 22:37
  • $\begingroup$ @MillieSmith The paper in the link only claims $\gamma(G)=\gamma^i(G)$, and the one in question is indeed wrong. $\endgroup$
    – Wei Zhan
    Mar 13, 2015 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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