Finding kernels in special digraphs

From Egres Open
Jump to: navigation, search

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

Deciding kernel-perfectness

Polyhedral description of kernels

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

References

  1. 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
  2. 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
  3. R. W. Irwing, An efficient algorithm for the stable roommates problem, J. Algorithms 6 (1985), 577-595. DOI link
  4. 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
  5. P. Arpin, V. Linek, Reachability problems in edge-colored digraphs, Discrete Mathematics 307 (2007), 2276–2289, DOI link
  6. R. Aharoni, E. Berger, I. Gorelik, Kernels in weighted digraphs, DOI link
  7. E. Boros, V. Gurvich, Perfect graphs are kernel solvable, Discrete Mathematics 159 (1996), 33-55, DOI link, Author link
  8. R. Aharoni, R. Holzman, Fractional kernels in digraphs, Journal of Combinatorial Theory Series B 73 (1998) 1-6, DOI link, Author link
  9. 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
  10. 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, DOI link, author link