# NP-hard problems on cographs

This question is similar to NP-hard problems on trees:

There is a large number of NP-complete problems that are tractable on cographs. 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 - 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?".

• 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? Feb 7, 2011 at 13:59
• 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). Feb 7, 2011 at 14:16

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. This is a formula for the "cocktail party graph", that is, the case where $n = 2$.

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

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

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

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

• 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  is a graph and an integer,  a graph and set of colors for each vertex,  two graphs. Feb 7, 2011 at 15:09
• 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? Jan 21, 2013 at 21:15

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 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.)

• Again, this can be reinterpreted as a problem on a single cograph (that happens to have two connected components). Jan 21, 2013 at 21:33
• 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. Jan 21, 2013 at 22:54
• 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$? Jan 22, 2013 at 0:14
• Ah, that is fine! Jan 22, 2013 at 0:20