4
$\begingroup$

EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org.


Likely this is technical error in graphclasses or in me.

Appears to me graphclasses claims P=NP.

In Domination perfect we have $\gamma(G)=i(G)$ which implies the complexity of Dominating Set (DS) and Independent Dominating Set (IDS) is the same in subclasses of domination perfect.

In line graphs we have DS NP-complete and IDS Polynomial.

According to the java application of graphclasses, line graphs are domination perfect, one of the reasons is they are claw-free.

Appears to me this implies P=NP.

What is wrong?

Screenshot:

enter image description here


Answering vb le question about polynomial IDS on line.

Clicking details recursively, we get: Polynomial on claw-free and the claim without reference on claw-free:

Polynomial On domination perfect graphs, the Independent set and Independent domininating set problems are equivalent.

$\endgroup$
  • 1
    $\begingroup$ I've found it straightforward to email Ernst to point out glitches and missing information, which have usually been fixed quickly. Graphclasses.org is a great community resource (and my sincere thanks to Ernst and everyone else who has contributed to it). $\endgroup$ – András Salamon Jan 26 '15 at 12:27
7
$\begingroup$

The culprit is the claim that Weighted-IDS is polynomial on claw-free graphs, because the independent set problem is and for domination perfect graphs, IDS is equivalent to IS. But for domination perfect graphs, IDS is not equivalent to IS, but to dominating set. So the statement should be: IDS is NPC on line graphs, because domination is.

$\endgroup$
  • $\begingroup$ Thanks, I suppose you MUST (as the RFCs say) fix this on graphclasses.org? $\endgroup$ – joro Jan 24 '15 at 14:58
  • 1
    $\begingroup$ Either that, or we 'fix' the definition of P/NP. The website was updated; you might have to force a reload to see the change. $\endgroup$ – Ernst de Ridder Jan 24 '15 at 15:52
  • $\begingroup$ Assuming you are in charge of graphclasses, I suggest you make it more it clear this was a BUG. $\endgroup$ – joro Jan 24 '15 at 16:27
6
$\begingroup$

Could you give a reference for your claim that IDS is polynomially for line graphs? Indeed, your proof for this fact would imply P=NP.

Yannakakis and Gavril proved in this paper that the the minimum maximal matching problem is NP-complete. This is exactly the independent domination problem on line graphs.

$\endgroup$
  • $\begingroup$ I edited answering your question. $\endgroup$ – joro Jan 24 '15 at 14:57
  • $\begingroup$ Just to be pedantic, I didn't claim IDS is in P for line. I claimed, graphclasses CLAIMED it is in P (nothing against graphclasses, bugs are everywhere). $\endgroup$ – joro Jan 24 '15 at 15:40
  • 3
    $\begingroup$ I see; thanks. Did you inform graphclasses about the bug before asking your question here? $\endgroup$ – vb le Jan 24 '15 at 15:55

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.