| Full text | |
| Author(s): |
De Carvalho, Marcelo H.
;
Kothari, Nishad
;
Wang, Xiumei
;
Lin, Yixun
Total Authors: 4
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 34, n. 3, p. 22-pg., 2020-01-01. |
| Abstract | |
A well-studied geometric object in combinatorial optimization is the perfect matching polytope of a graph G-the convex hull of the incidence vectors of all perfect matchings of G. In any investigation concerning the perfect matching polytope, one may assume that G is matching covered-that is, G is a connected graph (of order at least two) and each edge of G lies in some perfect matching. A graph G is Birkhoff-von Neumann if its perfect matching polytope is characterized solely by nonnegativity and degree constraints. A result of Balas [North Holland Math. Stud., 59 (1981), pp. 1-13] implies that G is Birkhoff-von Neumann 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 [T. Cominn. Theory Ser. B, 92 (2004), pp. 319-324]. More recently, these authors, along with Kothari [SIAM T. Discrete Math., 32 (2018), pp. 1478-1504], have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is (C-6) over bar -free. The combinatorial diameter of a polytope is the diameter of its 1-skeleton graph. A graph G is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. Independent results of Balinski and Russakoff [SIAM Rev., 16 (1974), pp. 516-525] and of Chvatal Cominn. Theory Ser. B, 18 (1975), pp. 138-154] imply that G is PM-compact if and only if G does not contain a pair of vertex-disjoint even cycles (C-1, C-2) such that G - V(C-1) - V(C-2) has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is near-bipartite-due to a result of Wang et al. [Discrete Math., 313 (2013), pp. 772-783]. In this paper, we consider the "intersection" of the aforementioned problems. We give an alternative description of matching covered graphs that are Birkhoff-von Neumann as well as PM -compact; our description implies that the corresponding decision problem is in P. (AU) | |
| FAPESP's process: | 18/04679-1 - Conformal minors and Pfaffian orientations |
| Grantee: | Nishad Bharat Kothari |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |