Title: Two unsolved problems: Birkhoff--von Neumann graphs and PM-compact graphs
| Speaker: | Nishad Kothari |
| Affiliation: | CSE Department, Indian Institute of Technology Madras |
| Zoom: | Contact Sharat Ibrahimpur |
Abstract:
A well-studied object in combinatorial optimization is the {\it perfect matching polytope} $\mathcal{PMP}(G)$ of a graph $G$ --- the convex hull of the incidence vectors of all perfect matchings of $G$. A graph $G$ is {\it Birkhoff--von Neumann} if $\mathcal{PMP}(G)$ is characterized solely by non-negativity and degree constraints, and $G$ is {\it PM-compact} if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one.
Chv{\'a}tal (1973) provided a graph-theoretical ${\rm co}-{\bf NP}$ characterization of PM-compact graphs, and Balas (1981) provided one for Birkhoff--von Neumann graphs; there is a striking similarity between their results. However, so far, we do not know of any ${\bf NP}$ characterizations 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 provide a complete description of graphs that are Birkhoff--von Neumann as well as PM-compact. Consequently, the corresponding decision problem is in ${\bf P}$. For more details, see: https://arxiv.org/abs/1807.07339.
Prior to this, in a joint work with Cl{\'a}udio~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'. For more details, see:https://epubs.siam.org/doi/abs/10.1137/17M1138704.
I will present the necessary background, and describe our aforementioned results. The talk will be self-contained. I shall assume only basic knowledge of graph theory, and will not present any lengthy proofs.