Kernel-perfectness
Contents
Games, kernels, marriages
A kernel in a directed graph is a set S of nodes with the following two properties:
- S is a stable set, i.e. There is no arc induced by S
- For any u in V-S, there is an arc uv such that v is in S.
This notion was originally introduced by von Neumann and Morgenstern [1] as a solution concept in cooperative game theory. From this perspective, kernels can be seen as an abstract model for the stability of a set of behaviours (or rules) in a society or in a group of individuals. Let V be a set of possible behaviours of various groups, and define a digraph by adding an arc uv if some subgroup would rather behave according to v instead of u. Intuitively, if S is a kernel in this digraph, then there is no pressure to change from one behaviour to another inside S, but for any behaviour outside of S there is some pressure to change to a behaviour in S.
A well-known example is the stable marriage problem. To formulate it in terms of kernels, let V be the set of possible marriages, and if u and v are marriages featuring the same person, then the arc uv is in the digraph if and only if this person prefers marriage v to marriage u. A kernel in this digraph corresponds to a stable marriage scheme. Notice that the digraph that we defined is an orientation of the line graph of the graph representing the possible marriages.
The Gale-Shapley algorithm finds a stable matching efficiently, but how hard it is to find a kernel in general? It turns out that it is much more difficult: the existence of a kernel is NP-complete to decide, even in subcubic planar digraphs [2].
The simplest example of a digraph that has no kernel is an odd directed cycle. By adding a new node and connecting every node of the cycle to this new node, we obtain a digraph with a kernel. This shows that existence of kernels is not monotone under taking subgraphs, so it makes sense to study kernel-perfect digraphs: digraphs where every induced sub-digraph has a kernel.
Some examples
It is easy to see that every acyclic digraph is kernel-perfect. In fact, every acyclic digraph has a single kernel, obtained by iteratively including all sinks and removing all sinks along with their in-neighbours from the digraph. Actually, this unique kernel coincides with the set of losing positions in the combinatorial impartial game defined by the digraph, so the winning strategy is to always move into the kernel.
There are several weaker sufficient conditions for kernel-perfectness: if every odd directed cycle has at least two symmetric arcs (Duchet [3]); if every directed cycle has at least one symmetric arc [3]; if every odd directed cycle has at least two chords with consecutive heads (Galeana-Sánchez and Neumann-Lara [4]); if D is the union of two transitive acyclic digraphs (Fleiner [5]). However, there is not much hope for obtaining a necessary and sufficient condition that is a good characterization. As we will see, the problem of deciding kernel-perfectness is unlikely to be in NP. It is also open whether it is in co-NP; this would require a certificate that there is a sub-digraph with no kernel, so we would need special sub-digraphs that are certifiably kernel-less. In the following, we look at graph classes where the existence of such sub-digraphs is guaranteed.
Kernel-perfectness of orientations
Kernels in orientations of line graphs are closely related to stable matchings. Borodin, Kostochka, and Woodall [6] showed that an orientation of a line multigraph is kernel-perfect if and only if every clique and every odd hole has a kernel (here cliques and odd holes are allowed to have oppositely oriented pairs of parallel edges). This is a co-NP characterization since it is easy to decide if a given clique or odd hole has a kernel. Interestingly, the same condition is necessary and sufficient for orientations of h-perfect multigraphs [7]. The latter theorem is a slight generalization of a famous result of Boros and Gurvich [8] that orientations of perfect multigraphs (perfect graphs with possible parallel edges) are kernel perfect if and only if every clique has a kernel.
A graph can have an exponential number of cliques, so it is not clear how to check if every clique has a kernel. Many of us thought that this should be tractable at least for perfect graphs; however, Andres and Hochstättler [9] managed to prove that this decision problem is co-NP-complete. Of course, this implies that the problem of deciding kernel-perfectness in not in NP unless NP=co-NP. In contrast, the kernel-perfectness of a line multigraph can be decided in polynomial time [6].
Questions
The above results suggest the following questions.
- Are there other interesting classes of graphs where the kernel-perfectness of an orientation can be decided efficiently? Claw-free graphs may be a good candidate, although Borodin, Kostochka and Woodall showed that the existence of kernels in all cliques and odd holes is not sufficient in this case.
- Is there some natural graph class, generalizing line graphs or h-perfect graphs (or both), where kernel-perfectness of an orientation is in co-NP?
Related open problems
Finding kernels in special digraphs
References
- ↑ J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, 1944, Princeton University Press
- ↑ 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.0 3.1 P. Duchet, Graphes Noyau-parfaits, Ann. Discrete Math. 9, 93-101, (1980), DOI link
- ↑ H. Galeana-Sánchez, V. Neumann-Lara, On Kernels and semikernels of digraphs, Discrete Math. 48, 67-76 (1984), DOI link
- ↑ T. Fleiner, Stable and crossing structures, Ph.D. dissertation, author link
- ↑ 6.0 6.1 O.V. Borodin, A.V. Kostochka, D.R. Woodall, On kernel-perfect orientations of line graphs, DOI link, author link
- ↑ T. Király, J. Pap, A note on kernels and Sperner's Lemma, Discrete Applied Mathematics 157 (2009),3327-3331. DOI link.
- ↑ E. Boros, V. Gurvich, Perfect graphs are kernel solvable, Discrete Mathematics 159 (1996), 33-55. DOI link. Author link.
- ↑ D. Andres, W. Hochstättler, Perfect digraphs, DOI link, technical report link
[ List view ]Comments
Please login to comment.