On Kernel Mengerian Orientations of Line Multigraphs

Abstract

We present a polyhedral description of kernels in orientations of line multigraphs. Given a digraph $D$, let $FK(D)$ denote the fractional kernel polytope defined on $D$, and let $\sigma (D)$ denote the linear system defining $FK(D)$. A digraph $D$ is called kernel perfect if every induced subdigraph $D^{\prime }$ has a kernel, called kernel ideal if $FK(D^{\prime })$ is integral for each induced subdigraph $D^{\prime }$, and called kernel Mengerian if $\sigma (D^{\prime })$ is TDI for each induced subdigraph $D^{\prime }$. We show that an orientation of a line multigraph is kernel perfect iff it is kernel ideal iff it is kernel Mengerian. Our result strengthens the theorem of Borodin et al. [3] on kernel perfect digraphs and generalizes the theorem of Kiraly and Pap [7] on stable matching problem.

arXiv comment12 pages, corrected and slightly expanded version