Deciding kernel-perfectness

From Egres Open
Jump to: navigation, search

What is the complexity of deciding kernel-perfectness in various classes of digraphs?


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


  1. E. Boros, V. Gurvich, Perfect graphs are kernel solvable, Discrete Mathematics 159 (1996), 33-55. DOI link. Author link.
  2. D. Andres, W. Hochstättler, Perfect digraphs, DOI link, technical report link
  3. O.V. Borodin, A.V. Kostochka, D.R. Woodall, On kernel-perfect orientations of line graphs, DOI link, author link
  4. T. Király, J. Pap, A note on kernels and Sperner's Lemma, Discrete Applied Mathematics 157 (2009),3327-3331. DOI link.