<p>Perhaps my favorite open problem is of interest: the edge clique-cover problem on cographs. In the edge clique-cover problem, you want to cover the edges of the cograph with a minimal number of cliques. It is unknown if this problem is NP-complete.</p>

<p>To illustrate that the problem is probably hard, let $K_n^m$ be the complete multipartite graph with $m$ partite sets each of size $n$. This is a cograph. There exist $m - 2$ pairwise orthogonal Latin squares of order $n$ if and only if the edge clique-cover of $K_n^m$ is $n^2$. This was shown by <a href="http://www.sciencedirect.com/science/article/pii/S0012365X09003264">Park, Kim and 
 Sano</a>. This is a formula for the "cocktail party graph", that is, the case where $n = 2$. </p>

CC BY-SA 3.0
2013-01-31T01:07:35.940Z
2014-01-10T13:27:45.107Z
2014-01-10T13:27:45.107Z
Ton Kloks
<p>Here is an NP-complete problem for two given cographs rather than one which is very closed to the asked question. The recently posted <a href="http://arxiv.org/abs/1301.3979">paper</a> shows that deciding, for given cographs $G$ and $H$, if $H$ is a retract of $G$, is NP-complete. ($H$ is a retract of $G$ if there exist edge-preserving maps $\rho: V(G)\to V(H)$ and $\gamma: V(H)\to V(G)$ such that $\rho\circ \gamma : V(H)\to V(H)$ is the identity.)  </p>

CC BY-SA 3.0
2013-01-21T21:33:57.160Z
Again, this can be reinterpreted as a problem on a single cograph (that happens to have two connected components).
David Eppstein
CC BY-SA 3.0
2013-01-21T22:54:28.947Z
I see. Of course, one may ask for NP-complete problems where the input consists solely of a *connected*, undirected, unweighted cograph. I think, the question is quite interesting.
vb le
CC BY-SA 3.0
2013-01-22T00:14:06.587Z
But connected cographs are just the complements of disconnected cographs, so requiring connectivity makes very little difference to the formulations of these problems. E.g., here's a version for connected cographs: for $G$ a connected cograph whose complement has two components, let $G_1$ and $G_2$ be the subgraphs induced in $G$ by the vertices of these components, ordered so that $|V(G_1)|\le|V(G_2)|$. Is $G_1$ a retract of $G_2$?
David Eppstein
CC BY-SA 3.0
2013-01-22T00:20:18.977Z
Ah, that is fine!
vb le
CC BY-SA 3.0
2013-01-21T13:10:02.543Z
2013-01-21T13:10:02.543Z
vb le
<p>Several problems remain NP-complete when restricted to cographs. List coloring, achromatic
number, and Induced subgraph isomorphism remain NP-complete. </p>

<p>[1] Hans L. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs. Inf. Process. Lett., 31(3):135–138, 1989 </p>

<p>[2] Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Appl. Math.,
75(2):135–155, 1997</p>

<p>[3] Peter Damaschke. Induced subgraph isomorphism for cographs is NP-complete. Lecture Notes in Computer Science, 1991, Volume 484/1991, 72-78,</p>

CC BY-SA 3.0
2013-01-21T21:15:55.637Z
Here are trivial variations of two of the same problems that remain NP-complete but only have a cograph as input: does the given cograph consist of two connected components, one of which is an induced subgraph of the other? Does the given cograph have a complete coloring that gives each of its isolated vertices a distinct color?
David Eppstein
CC BY-SA 2.5
2011-02-07T15:09:59.000Z
Thanks a lot for your answer. These are really interesting problems, but I think they do not meet the requirement that the input is only a graph: The input in [1] is a graph and an integer, [2] a graph and set of colors for each vertex, [3] two graphs.
Martin Lackner
CC BY-SA 2.5
2011-02-07T14:15:36.320Z
2011-02-07T14:24:33.310Z
2011-02-07T14:24:33.310Z
Mohammad Al-Turkistany
<p>This question is similar to <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">NP-hard problems on trees</a>:</p>

<p><strong>There is a large number of NP-complete problems that are tractable on <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow noreferrer">cographs</a>. Are there any known problems that remain NP-complete when restricted to cographs?</strong></p>

<p>To be more precise I am interested in examples where the input consists <strong>solely of an undirected, unweighted cograph</strong>.</p>

<p>Two remarks:</p>

<ul>
<li><p>For weighted cographs such a problem is mentioned <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees/1218#1218">here</a> - TSP with two travellers</p></li>
<li><p>Cographs are the "base class" of clique-width such as trees are the base class for tree-width.</p></li>
</ul>

<p><strong>UPDATE</strong></p>

<p>Some further thoughts (I am not quite sure about):
If the input is really just a cograph, the question has to be of the sort "Does the cograph have property X?". It would be enough if such a problem existed for trees, since then the question could be "Does the cotree of the cograph have property X?".</p>

CC BY-SA 2.5
2011-02-07T13:59:03.723Z
So, preventing from being as a (not so) duplicated question, maybe we also require these NP-complete problems to be polynomial time solvable on trees?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-07T14:16:56.423Z
Would be nice of course. However I would be contended even if this was not the case. Especially since all examples given in the original thread do not answer my question (to my understanding).
Martin Lackner
<cc.complexity-theory><np-hardness><graph-algorithms>
NP-hard problems on cographs
Martin Lackner
# NP-hard problems on cographs

(Asked by: username_0 on 2011-02-07)

This question is similar to [NP-hard problems on trees](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees):

**There is a large number of NP-complete problems that are tractable on [cographs](http://en.wikipedia.org/wiki/Cograph). Are there any known problems that remain NP-complete when restricted to cographs?**

To be more precise I am interested in examples where the input consists **solely of an undirected, unweighted cograph**.

Two remarks:

* For weighted cographs such a problem is mentioned [here](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees/1218#1218) - TSP with two travellers
* Cographs are the "base class" of clique-width such as trees are the base class for tree-width.

**UPDATE**

Some further thoughts (I am not quite sure about):
If the input is really just a cograph, the question has to be of the sort "Does the cograph have property X?". It would be enough if such a problem existed for trees, since then the question could be "Does the cotree of the cograph have property X?".

**Tags:** cc.complexity-theory, np-hardness, graph-algorithms
> **Comments:**
> **username_1**: So, preventing from being as a (not so) duplicated question, maybe we also require these NP-complete problems to be polynomial time solvable on trees?  
> **username_0**: Would be nice of course. However I would be contended even if this was not the case. Especially since all examples given in the original thread do not answer my question (to my understanding).  

---

## 3 answers

### Answer by username_2 on 2013-01-31. Score: 11

Perhaps my favorite open problem is of interest: the edge clique-cover problem on cographs. In the edge clique-cover problem, you want to cover the edges of the cograph with a minimal number of cliques. It is unknown if this problem is NP-complete.

To illustrate that the problem is probably hard, let $K\_n^m$ be the complete multipartite graph with $m$ partite sets each of size $n$. This is a cograph. There exist $m - 2$ pairwise orthogonal Latin squares of order $n$ if and only if the edge clique-cover of $K\_n^m$ is $n^2$. This was shown by [Park, Kim and
Sano](http://www.sciencedirect.com/science/article/pii/S0012365X09003264). This is a formula for the "cocktail party graph", that is, the case where $n = 2$.


---

### Answer by username_3 on 2013-01-21. Score: 10

Here is an NP-complete problem for two given cographs rather than one which is very closed to the asked question. The recently posted [paper](http://arxiv.org/abs/1301.3979) shows that deciding, for given cographs $G$ and $H$, if $H$ is a retract of $G$, is NP-complete. ($H$ is a retract of $G$ if there exist edge-preserving maps $\rho: V(G)\to V(H)$ and $\gamma: V(H)\to V(G)$ such that $\rho\circ \gamma : V(H)\to V(H)$ is the identity.)

> **Comments:**
> **username_4**: Again, this can be reinterpreted as a problem on a single cograph (that happens to have two connected components).  
> **username_3**: I see. Of course, one may ask for NP-complete problems where the input consists solely of a *connected*, undirected, unweighted cograph. I think, the question is quite interesting.  
> **username_4**: But connected cographs are just the complements of disconnected cographs, so requiring connectivity makes very little difference to the formulations of these problems. E.g., here's a version for connected cographs: for $G$ a connected cograph whose complement has two components, let $G_1$ and $G_2$ be the subgraphs induced in $G$ by the vertices of these components, ordered so that $|V(G_1)|\le|V(G_2)|$. Is $G_1$ a retract of $G_2$?  
> **username_3**: Ah, that is fine!  

---

### Answer by username_5 on 2011-02-07. Score: 10

Several problems remain NP-complete when restricted to cographs. List coloring, achromatic
number, and Induced subgraph isomorphism remain NP-complete.

[1] Hans L. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs. Inf. Process. Lett., 31(3):135–138, 1989

[2] Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Appl. Math.,
75(2):135–155, 1997

[3] Peter Damaschke. Induced subgraph isomorphism for cographs is NP-complete. Lecture Notes in Computer Science, 1991, Volume 484/1991, 72-78,

> **Comments:**
> **username_0**: Thanks a lot for your answer. These are really interesting problems, but I think they do not meet the requirement that the input is only a graph: The input in [1] is a graph and an integer, [2] a graph and set of colors for each vertex, [3] two graphs.  
> **username_4**: Here are trivial variations of two of the same problems that remain NP-complete but only have a cograph as input: does the given cograph consist of two connected components, one of which is an induced subgraph of the other? Does the given cograph have a complete coloring that gives each of its isolated vertices a distinct color?  

---

