Theoretical Statistics and Mathematics Unit, ISI Delhi

February 18, 2020 (Tuesday) ,
3:30 PM at Webinar

Speaker:
Nishad Kothari,
University of Campinas

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

Abstract of Talk

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.