7
$\begingroup$

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.

According to VIZING’S CONJECTURE FOR CHORDAL GRAPHS, p.1

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?

$\endgroup$
16
$\begingroup$

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:

example

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.

$\endgroup$
  • $\begingroup$ Thanks, indeed there are counterexamples to gamma(G)=i(G) for chordal. $\endgroup$ – joro Mar 12 '15 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$ – Millie Smith Mar 12 '15 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$ – Willard Zhan Mar 13 '15 at 1:48

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.