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.

Improve this question
$\endgroup$
1
  • 2
    $\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
    Commented Jan 26, 2015 at 12:27

2 Answers 2

Reset to default
8
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I suppose you MUST (as the RFCs say) fix this on graphclasses.org? $\endgroup$
    – joro
    Commented Jan 24, 2015 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
    Commented Jan 24, 2015 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
    Commented Jan 24, 2015 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I edited answering your question. $\endgroup$
    – joro
    Commented Jan 24, 2015 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
    Commented Jan 24, 2015 at 15:40
  • 3
    $\begingroup$ I see; thanks. Did you inform graphclasses about the bug before asking your question here? $\endgroup$
    – vb le
    Commented Jan 24, 2015 at 15:55

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.