Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 7 '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 7 '11 at 14:16
add comment

3 Answers 3

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,

share|improve this answer
    
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 7 '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
add comment

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

share|improve this answer
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 0:14
    
Ah, that is fine! –  vb le Jan 22 '13 at 0:20
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.