Tata Institute of Fundamental Research
Two unsolved problems: Birkhoff-von Neumann graphs and PM-compact graphs
STCS Seminar
Speaker:
Nishad Kothari (The University of Campinas
SP, Brazil)
Organiser:
Umang Bhaskar
Date:
Tuesday, 19 Feb 2019, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Nishad Kothari (The University of Campinas SP, Brazil) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 19 Feb 2019, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.