University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Combinatorial Optimization Reading Group - Nishad KothariExport this event to calendar

Friday, July 17, 2020 — 1:30 PM EDT

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.

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2021 (58)
    1. June (11)
    2. May (7)
    3. April (9)
    4. March (13)
    5. February (8)
    6. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)