| Title | : | Two unsolved problems: Birkhoff-von Neumann graphs and PM-compact graphs |
| Speaker | : | Nishad Kothari (University of Campinas) |
| Details | : | Thu, 30 Jan, 2020 2:00 PM @ AM Turing Hall |
| 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 match- ings of G. A graph G is Birkho {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. Chv atal (1973) provided a graph-theoretical co-NP characterization of PM-compact graphs, and Balas (1981) provided one for Birkho {von Neumann graphs; there is a striking similarity between their results. However, so far, we do not know of any 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 Birkho {von Neumann as well as PM-compact. Consequently, the corre- sponding decision problem is in P. For more details, see: https://arxiv.org/abs/1807.07339. Prior to this, in a joint work with Cl audio L. Lucchesi, Marcelo H. de Carvalho and U. S. R. Murty, we showed that the problem of deciding whether a graph G is Birkho { 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. |
