# Finding kernels in special digraphs

In which classes of digraphs can we decide if a kernel exists and find one in polynomial time?

## Remarks

Richardson's theorem states that every digraph without a directed odd cycle has a kernel, and the proof gives rise to an algorithm to find one. On the other hand, Chvátal ^{[1]} showed that in general it is NP-complete to decide if a digraph has a kernel, and by a result of Fraenkel ^{[2]} it is NP-complete even in planar directed graphs of degree at most 3.

One interesting special case is related to the fact that a stable matching (if it exists) can be found in polynomial time in any graphic preference system ^{[3]}. This implies the following for kernels: *If D is an orientation of a line graph and every clique is acyclic in D, then a kernel can be found in polynomial time (if it exists)*.

Another known case is when the digraph is the union of two transitive subdigraphs. In this case the Sands-Sauer-Woodrow theorem states that a kernel always exists, and it can be found in polynomial time by an analogue of the Gale-Shapley algorithm (^{[4]}, see also Theorem 5.4 in ^{[5]}). Aharoni, Berger, and Gorelik ^{[6]} proved a weighted version of this theorem, using a more involved argument.

## (Super)orientations of perfect graphs

It has been proved by Boros and Gurvich ^{[7]} that perfect graphs are kernel solvable, i.e. if the underlying undirected graph of a digraph *D* is perfect and in every clique the subgraph of one-way arcs is acyclic, then *D* has a kernel. Later, a shorter proof using Scarf's Lemma has been found by Aharoni and Holzman ^{[8]}, and a short proof based on Sperner's Lemma was given by Király and Pap ^{[9]}. However, none of these proofs provide a polynomial algorithm to find a kernel. Király and Pap ^{[9]} extended the above results to h-perfect graphs: if the underlying undirected graph of a digraph *D* is h-perfect, no odd hole is a directed cycle of one-way arcs, and in every clique the subgraph of one-way arcs is acyclic, then *D* has a kernel. Since the structure of h-perfect graphs is less understood than perfect graphs, it is probably more difficult to find kernels in this class.

A subclass of perfect graphs where a polynomial algorithm exists is the class of DE graphs. It was shown in ^{[10]} that a kernel can be found in polynomial time in a clique-acyclic orientation of a DE graph. This was extended to clique-acyclic super-orientations (where oppositely oriented parallel edges are allowed) by Pass-Lanneau, Igarashi, and Meunier ^{[11]}. They also gave polynomial-time algorithms for the following two classes:

- clique-acyclic orientations of claw-free perfect graphs,
- clique-acyclic super-orientations of chordal graphs.

## Related problems

Polyhedral description of kernels

See also the blog post Blog:Tidbits/Kernel-perfectness

## References

- ↑ V. Chvátal,
*On the computational complexity of finding a kernel*, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal (1973), Author link - ↑ A.S. Fraenkel,
*Planar kernel and grundy with [math]d \leq 3[/math], [math]d_{out} \leq 2[/math], [math]d_{in} \leq 2[/math] are NP-complete*, Discrete Appl. Math. 3 (1981) 257-262. DOI link - ↑ R. W. Irwing,
*An efficient algorithm for the stable roommates problem*, J. Algorithms 6 (1985), 577-595. DOI link - ↑ B. Sands, N. Sauer, R. Woodrow,
*On monochromatic paths in edge-coloured digraphs*, J. Comb. Theory Ser. B 33 (1982), 271–275, DOI link, ResearchGate link - ↑ P. Arpin, V. Linek,
*Reachability problems in edge-colored digraphs*, Discrete Mathematics 307 (2007), 2276–2289, DOI link - ↑ R. Aharoni, E. Berger, I. Gorelik,
*Kernels in weighted digraphs*(2014), DOI link - ↑ E. Boros, V. Gurvich,
*Perfect graphs are kernel solvable*, Discrete Mathematics 159 (1996), 33-55, DOI link, Author link - ↑ R. Aharoni, R. Holzman,
*Fractional kernels in digraphs*, Journal of Combinatorial Theory Series B 73 (1998) 1-6, DOI link, Author link - ↑
^{9.0}^{9.1}T. Király, J. Pap,*A note on kernels and Sperner's Lemma*, Discrete Applied Mathematics 157 (2009),3327-3331. DOI link - ↑ O. Durand de Gevigney, F. Meunier, C. Popa, J. Reygner, A. Romero-Campos,
*Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree*(2011), DOI link, author link - ↑ A. Pass-Lanneau, A. Igarashi, F. Meunier,
*Perfect graphs with polynomially computable kernels*(2018), arXiv link