Sands-Sauer-Woodrow theorem
In a directed graph D=(V,A), a kernel is an independent set [math]X \subseteq V[/math] with the property that for each node [math]u \in V \setminus X[/math] there is a node [math]v \in X[/math] such that [math]uv \in A[/math]; see Kernel (in digraph).
Theorem (Sands, Sauer, Woodrow [1]). If a digraph D is the union of two transitive subdigraphs, then D has a kernel.
A kernel can be found in polynomial time by a generalization of the Gale-Shapley algorithm. Contrary to bipartite stable matchings, finding a minimum cost kernel in the union of two transitive subdigraphs is NP-hard, because it is NP-complete to decide if there is a kernel containing a given node (see Theorem 20.7 in [2]).
Related pages
Skew-supermodular list colouring
Finding kernels in special digraphs
References
- ↑ 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
- ↑ T. Fleiner, Stable and crossing structures, Ph.D. dissertation, author link
