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