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.

(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

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 (2014), 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 (2011), DOI link, author link
  11. ↑ A. Pass-Lanneau, A. Igarashi, F. Meunier, Perfect graphs with polynomially computable kernels (2018), arXiv link
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Finding_kernels_in_special_digraphs&oldid=2437"