Chennai Mathematical Institute

Seminars




3:30 pm, Seminar Hall
Two unsolved problems: Birkhoff–von Neumann graphs and PM-compact graphs

Nishad Kothari
Institute of Computing University of Campinas (UNICAMP), Brazil.
11-02-19


Abstract

A well-studied 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 such investigation, one may assume that G is matching covered — that is, G is a connected graph (on at least two vertices) 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 non-negativity and degree constraints. A result of Balas (1981) implies that G is Birkhoff–von Neumann if and only if G does not contain a pair of vertex-disjoint odd cycles (C1, C2) such that G − V(C1) − V(C2) 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). More recently, in a joint work with these three authors, we have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is ‘prism-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. A result of Chv'atal (1975) implies that G is PM-compact if and only if G does not contain a pair of vertex-disjoint even cycles (C1, C2) such that G − V(C1) − V(C2) has a perfect matching. Once again the corresponding decision problem is in co-N P, 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 results of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013). Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the “intersection” of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff–von Neumann as well as PM-compact. Thus the corresponding decision problem is in P.

I will discuss the two problems, and our recent results mentioned above. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. I will perhaps not present any lengthy proofs. For more details, see: https://arxiv.org/abs/1807.07339 and https://epubs.siam.org/doi/abs/10.1137/17M1138704.