Deciding kernel-perfectness
What is the complexity of deciding kernel-perfectness in various classes of digraphs?
Remarks
In general, it is not known if kernel-perfectness is in NP or co-NP. The page on Richardson's theorem describes some classes where kernel-perfectness can be decided in polynomial time.
It has been proved by Boros and Gurvich [1] that perfect graphs are kernel solvable. This result implies that a superorientation of a prefect graph is kernel-perfect if and only if it is clique-acyclic. Andres and Hochstättler [2] proved that it is co-NP-complete to decide if a superorientation of a prefect graph is clique-acyclic or not. This implies that deciding kernel-perfectness of superorientations of prefect graphs is also co-NP-complete.
Using the proof technique of Galvin's bipartite list-edge-colouring theorem, Borodin, Kostochka, and Woodall [3] proved that an orientation of the line graph of a multigraph is kernel-perfect if and only if the orientation is clique-acyclic and no odd hole is a directed cycle of one-way arcs (here the line graph contains two edges between nodes corresponding to parallel edges in the original multigraph).
Király and Pap [4] extended the result of Boros and Gurvich to h-perfect graphs: if the underlying undirected graph of a digraph D is h-perfect, D is clique-acyclic, and no odd hole is a directed cycle of one-way arcs, then D has a kernel. This characterizes kernel-perfectness of superorientations of h-perfect graphs, so the problem is in co-NP for this class too.
Related problems
Finding kernels in special digraphs
Polyhedral description of kernels
See also the blog post Blog:Tidbits/Kernel-perfectness
References
- ↑ E. Boros, V. Gurvich, Perfect graphs are kernel solvable, Discrete Mathematics 159 (1996), 33-55. DOI link. Author link.
- ↑ D. Andres, W. Hochstättler, Perfect digraphs, DOI link, technical report link
- ↑ O.V. Borodin, A.V. Kostochka, D.R. Woodall, On kernel-perfect orientations of line graphs, DOI link, author link
- ↑ T. Király, J. Pap, A note on kernels and Sperner's Lemma, Discrete Applied Mathematics 157 (2009),3327-3331. DOI link.
