# Weird claim of graphclasses about complexity of domination

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:

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.

• 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). Jan 26 '15 at 12:27

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.

• Thanks, I suppose you MUST (as the RFCs say) fix this on graphclasses.org?
– joro
Jan 24 '15 at 14:58
• 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. Jan 24 '15 at 15:52
• Assuming you are in charge of graphclasses, I suggest you make it more it clear this was a BUG.
– joro
Jan 24 '15 at 16:27

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.