3
$\begingroup$

Is there anything known about the hardness of Vertex Cover on the subclass of comparability graphs? In particular, is it known whether the problem is still NP-hard?

Related Results: In "Modular decomposition and transitive orientation, McConnell & Spinrad, 1999" the authors show that the problem lies in P for co-comparability graphs. According to Wikipedia is is also known to lie in P for perfect graphs, but I haven't been able to find any results on comparability graphs.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Vertex cover for comparability graphs is solvable in P-time:

  1. Comparability graphs are (strongly) perfect ("Strongly Perfect Graphs", Berge & Duchet, 1984)
  2. Independent set is P-time on perfect graphs (https://en.wikipedia.org/wiki/Perfect_graph)
  3. The complement of an independent set is a vertex cover, and vice versa

Independent set for comparability graphs is also listed as "Polynomial" at section "Unweighted problems" on the page of comparability graphs at at ISGCI.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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