Two unsolved problems: Birkhoff-von Neumann graphs and PM-compact graphs

Abstract:  A well-studied object in combinatorial optimization is the perfect matching polytope PMP(G) of a graph G - the convex hull of the incidence vectors of all perfect matchings of G. A graph G is Birkhoff-von Neumann if PMP(G) is characterized solely by non-negativity and degree constraints, and G is PM-compact if the combinatorial diameter of PMP(G) equals one. Chvatal (1973) provided a graph-theoretical co - NP characterization of PM-compact graphs, and Balas (1981) provided one for Birkhoff-von Neumann graphs; there is a striking similarity between their characterizations. However, so far, we do not know of any NP characterization for either of these graph classes.

Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the "intersection" of these graph classes. We give a complete characterization of graphs that are Birkhoff-von Neumann as well as PM-compact. Consequently, the corresponding decision problem is in P. Earlier, in a joint work with Claudio L. Lucchesi, Marcelo H. de Carvalho and U. S. R. Murty, we showed that the problem of deciding whether a graph G is Birkhoff-von Neumann is equivalent to the seemingly unrelated problem of deciding whether G is `prism-free'.

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.