Polyhedral description of kernels

From Egres Open
Jump to: navigation, search

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 [1] 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 [2] 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.

Kernel1.png

Rothblum's (and Király and Pap's) result was extended by Chen, Ding, Hu, and Zang [3] to line graphs of non-bipartite graphs for which the first phase of Irving's stable matching algorithm [4] 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 [5]. 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.

References

  1. U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Programming Ser. A 54 (1992), 57–67. DOI link.
  2. T. Király, J. Pap, Total dual integrality of Rothblum's description of the stable marriage polyhedron, journal link, EGRES technical report
  3. X. Chen, G. Ding, X. Hu, W. Zang, The maximum-weight stable matching problem: duality and efficiency, DOI link, author link
  4. R. W. Irving, An efficient algorithm for the stable roommates problem, DOI link
  5. T. Fleiner, Stable and crossing structures, Ph.D. dissertation, author link