12

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?".

Community
  • 1
Martin Lackner
  • 443
  • 2
  • 7
  • 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 張顯之 Feb 07 '11 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). – Martin Lackner Feb 07 '11 at 14:16

3 Answers3

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

Peng O
  • 125
  • 2
  • 6
Ton Kloks
  • 111
  • 1
  • 2
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 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.)

vb le
  • 4,828
  • 1
  • 37
  • 46
  • 2
    Again, this can be reinterpreted as a problem on a single cograph (that happens to have two connected components). – David Eppstein Jan 21 '13 at 21:33
  • 1
    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 Jan 21 '13 at 22:54
  • 1
    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 Jan 22 '13 at 00:14
  • Ah, that is fine! – vb le Jan 22 '13 at 00:20
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,

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 1
    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 Feb 07 '11 at 15:09
  • 3
    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 Jan 21 '13 at 21:15