A Polyhedral Description of Kernels

• 成果类型: Article
• 署名作者: Chen, Qin; Chen, Xujin; Zang, Wenan
• 署名单位: China Jiliang University; Chinese Academy of Sciences; University of Hong Kong
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0764
• 发表日期: 2016
• 页码: 969-990
• 关键词: digraphs

摘要

Let G be a digraph and let pi(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if pi(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if pi(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-time algorithm for the minimum weighted kernel problem on kernel ideal digraphs. We also prove that it is NP-hard to find a kernel of minimum size even in a planar bipartite digraph with maximum degree at most three.