<p>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.</p>

<p>Yannakakis and Gavril proved in <a href="http://epubs.siam.org/doi/abs/10.1137/0138030">this paper</a> that the the minimum maximal matching problem is NP-complete. This is exactly the independent domination problem on line graphs.</p>

CC BY-SA 3.0
2015-01-24T14:57:43.890Z
I edited answering your question.
joro
CC BY-SA 3.0
2015-01-24T15:40:10.697Z
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).
joro
CC BY-SA 3.0
2015-01-24T15:55:31.743Z
I see; thanks. Did you inform graphclasses about the bug before asking your question here?
vb le
CC BY-SA 3.0
2015-01-24T14:42:50.367Z
2015-01-24T14:42:50.367Z
vb le
<p>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.</p>

CC BY-SA 3.0
2015-01-24T14:58:57.650Z
Thanks, I suppose you MUST (as the RFCs say) fix this on graphclasses.org?
joro
CC BY-SA 3.0
2015-01-24T15:52:38.697Z
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.
Ernst de Ridder
CC BY-SA 3.0
2015-01-24T16:27:55.037Z
Assuming you are in charge of graphclasses, I suggest you make it more it clear this was a BUG.
joro
CC BY-SA 3.0
2015-01-24T14:42:27.350Z
2015-01-24T14:42:27.350Z
Ernst de Ridder
<p><strong>EDIT</strong> this got <em>'fixed'</em> on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - <a href="http://sagemath.org" rel="nofollow noreferrer">http://sagemath.org</a>.</p>

<hr>

<p>Likely this is technical error in graphclasses or in me.</p>

<p>Appears to me graphclasses claims P=NP.</p>

<p>In <a href="http://graphclasses.org/classes/gc_549.html" rel="nofollow noreferrer">Domination perfect</a>
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.</p>

<p>In <a href="http://graphclasses.org/classes/gc_249.html" rel="nofollow noreferrer">line graphs</a>
we have DS NP-complete and IDS Polynomial.</p>

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

<p>Appears to me this implies P=NP.</p>

<blockquote>
  <p>What is wrong?</p>
</blockquote>

<p>Screenshot:</p>

<p><img src="https://i.sstatic.net/PwoTm.png" alt="enter image description here"></p>

<hr>

<p>Answering vb le question about polynomial IDS on line.</p>

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

<blockquote>
  <p>Polynomial On domination perfect graphs, the Independent set and Independent domininating set problems are equivalent. </p>
</blockquote>

CC BY-SA 3.0
2015-01-26T12:27:16.043Z
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).
András Salamon
<graph-theory><co.combinatorics><graph-classes>
Weird claim of graphclasses about complexity of domination
joro
# Weird claim of graphclasses about complexity of domination

(Asked by: username_0 on 2015-01-24)

**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](http://graphclasses.org/classes/gc_549.html)
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](http://graphclasses.org/classes/gc_249.html)
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](https://i.sstatic.net/PwoTm.png)

---

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.

**Tags:** graph-theory, co.combinatorics, graph-classes
> **Comments:**
> **username_1**: 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).  

---

## 2 answers

### Answer by username_3 on 2015-01-24. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, I suppose you MUST (as the RFCs say) fix this on graphclasses.org?  
> **username_3**: 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.  
> **username_0**: Assuming you are in charge of graphclasses, I suggest you make it more it clear this was a BUG.  

---

### Answer by username_2 on 2015-01-24. Score: 6

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](http://epubs.siam.org/doi/abs/10.1137/0138030) that the the minimum maximal matching problem is NP-complete. This is exactly the independent domination problem on line graphs.

> **Comments:**
> **username_0**: I edited answering your question.  
> **username_0**: 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).  
> **username_2**: I see; thanks. Did you inform graphclasses about the bug before asking your question here?  

---

