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

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.

## Related problems

2. A.S. Fraenkel, Planar kernel and grundy with $d \leq 3$, $d_{out} \leq 2$, $d_{in} \leq 2$ are NP-complete, Discrete Appl. Math. 3 (1981) 257-262. DOI link