Polyhedral description of kernels

For which classes of digraphs can we explicitly give a linear description of the convex hull of kernels?

Remarks

Since kernels are stable sets, any inequality valid for stable sets can be used. Additionally, the following inequalities must hold if x is the characteristic vector of a kernel of the digraph D=(V,A):

(1) [math]x(v)+x(N^{out}(v)) \geq 1[/math] for every [math]v \in V[/math].

By a result of Rothblum on stable matchings, clique inequalities and inequalities of type (1) describe the convex hull of kernels if the underlying undirected graph of D is the line graph of a bipartite graph, and every clique is acyclic. Király and Pap showed that in this case the linear system is TDI. The condition that every clique is acyclic is important: the figure on the left below represents an orientation of the line graph of [math]K_{3,3}[/math] (each 3-clique is a cycle) where there is no kernel, but the all-1/3 vector satisfies the inequalities of type (1).

The figure on the right is an example by Frédéric Meunier showing an oriented simple bipartite graph with a vector on the nodes that satisfies the inequalities of type (1) but is not a convex combination of kernels, since each kernel has size 3.

Rothblum's (and Király and Pap's) result was extended by Chen, Ding, Hu, and Zang to line graphs of non-bipartite graphs for which the first phase of Irving's stable matching algorithm gives a bipartite graph.

If D is an acyclic digraph, then the polyhedral description is trivial: in this case there is one kernel, and its characteristic vector is the only vector satisfying (1) and [math]x(u)+x(v) \leq 1[/math] for every [math]uv \in A[/math].

If D is the union of two transitive acyclic subdigraphs, then a kernel always exists. In other words, any two partial orders have a stable common antichain, see the PhD dissertation of Fleiner . However, Fleiner also shows that deciding whether there is a stable common antichain containing a given element is NP-complete, so a compact polyhedral description of kernels is unlikely in this case.

Another relevant result of the dissertation of Fleiner to this topic is that there is a large class of kernel problems, defined by a pair of increasing co-monotone set functions, where a polyhedral description can be given implicitly using blockers, and we can optimize over the polyhedron in polynomial time using the ellipsoid method. Special cases include the stable matching problem in bipartite graphs and matroid kernel problem .