Birkhoff-von Neumann graphs that are PM-compact

DOI10.1137/18M1202347MaRDI QIDQ5130578zbMATH OpenOpenAlexFDO

Authors Marcelo H. de Carvalho, Nishad Kothari, Xiumei Wang, Yanpei Liu

Publication date 28 October 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.07339

zbMATH Keywords

Birkhoff-von Neumann graphmatching covered graphperfect matchingperfect matching polytopePM-compact graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Combinatorial optimization (90C27)

Abstract: A well-studied geometric object in combinatorial optimization is the perfect matching polytope of a graph $G$. In any investigation concerning the perfect matching polytope, one may assume that $G$ is matching covered --- that is, it is a connected graph (of order at least two) and each edge lies in some perfect matching. A graph $G$ is Birkhoff-von Neumann (BvN) if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that $G$ is BvN if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar --- due to a result of Carvalho, Lucchesi and Murty (2004). These authors, along with Kothari (2018), have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is $overline{C}_6$-free. The combinatorial diameter of a polytope is the diameter of its $1$-skeleton graph. A graph $G$ is PM-compact (PMc) if the combinatorial diameter of its perfect matching polytope equals one. A result of Chv'atal (1975) implies that $G$ is PMc if and only if $G$ does not contain a pair of vertex-disjoint even cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is near-bipartite --- due to a result of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013). In this paper, we consider the "intersection" of the aforementioned problems. We give a complete characterization of matching covered graphs that are BvN as well as PMc. (Thus the corresponding decision problem is in P.)

Recommendations

• A characterization of PM-compact Hamiltonian bipartite graphs
• PM-compact graphs and vertex-deleted subgraphs
• A characterization of PM-compact bipartite and near-bipartite graphs
• A note on PM-compact bipartite graphs
• A compact linear program for testing optimality of perfect matchings.

Cites work

• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• A characterization of PM-compact bipartite and near-bipartite graphs
• A characterization of PM-compact claw-free cubic graphs
• A characterization of PM-compact Hamiltonian bipartite graphs
• Brick decompositions and the matching rank of graphs
• Generating bricks
• Graphs with independent perfect matchings
• How to build a brick
• scientific article; zbMATH DE number 3078983 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Integer and Fractional Matchings
• Matching structure and the matching lattice
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On certain polytopes associated with graphs
• On the Assignment Polytope
• On two unsolved problems concerning matching covered graphs
• The perfect matching polytope and solid bricks

Cited in

(7)

• Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
• A characterization of PM-compact bipartite and near-bipartite graphs
• Relations between global forcing number and maximum anti-forcing number of a graph
• PM-compact graphs and vertex-deleted subgraphs
• A characterization of PM-compact Hamiltonian bipartite graphs
• A note on PM-compact bipartite graphs
• Complete forcing numbers of complete and almost-complete multipartite graphs

This page was built for publication: Birkhoff-von Neumann graphs that are PM-compact

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130578)