# 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  showed that in general it is NP-complete to decide if a digraph has a kernel, and by a result of Fraenkel  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 . 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 (, see also Theorem 5.4 in ). Aharoni, Berger, and Gorelik  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  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 , and a short proof based on Sperner's Lemma was given by Király and Pap . However, none of these proofs provide a polynomial algorithm to find a kernel. Király and Pap  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  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 . 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.