patternMinor
Vertex Cover on Comparability Graphs
Viewed 0 times
covergraphscomparabilityvertex
Problem
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.
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.
Solution
Vertex cover for comparability graphs is solvable in P-time:
Independent set for comparability graphs is also listed as "Polynomial" at section "Unweighted problems" on the page of comparability graphs
at at ISGCI.
- Comparability graphs are (strongly) perfect ("Strongly Perfect Graphs", Berge & Duchet, 1984)
- Independent set is P-time on perfect graphs (https://en.wikipedia.org/wiki/Perfect_graph)
- 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.
Context
StackExchange Computer Science Q#160320, answer score: 2
Revisions (0)
No revisions yet.