solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看115次
Birkhoff-von Neumann Graphs that are PM-compact. (arXiv:1807.07339v1 [math.CO])
来源于:arXiv
A geometric object of great interest in combinatorial optimization is the
perfect matching polytope of a graph $G$. In any investigation concerning the
perfect matching polytope, one may assume that $G$ is matching covered --- that
is, it is a connected graph (of order at least two) and each edge lies in some
perfect matching.
A graph $G$ is Birkhoff-von Neumann (BvN) if its perfect matching polytope is
characterized solely by non-negativity and degree constraints. A result of
Balas (1981) implies that $G$ is BvN if and only if $G$ does not contain a pair
of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a
perfect matching. It follows immediately that the corresponding decision
problem is in co-NP. However, it is not known to be in NP. The problem is in P
if the input graph is planar --- due to a result of Carvalho, Lucchesi and
Murty (2004). These authors, along with Kothari (2018), have shown that this
problem is equivalent to the seemingly unrelated problem o 查看全文>>