On strong integrality properties of the perfect matching polytope
(2024) , 20 pages
Files
CORE_DP_2024-32.pdf
Open Access - Adobe PDF
- 1.07 MB
Details
- Authors
- Abstract
- This paper investigates integrality properties of perfect matching polytopes, focusing on box-total dual integrality and integer decomposition properties. We begin by characterizing the graphs whose perfect matching polytope is a slice of the nonnegative orthant, identifying these as the solid graphs introduced by de Carvalho, Lucchesi, and Murty in “On a Conjecture of Lovász Concerning Bricks: I. The Characteristic of a Matching Covered Graph” (Journal of Combinatorial Theory, Series B). As a result, we show that the perfect matching polytope of solid graphs admits a compact description, and we establish that deciding the box-total dual integrality of a perfect matching polytope can be done in polynomial time. Additionally, we characterize the conditions under which perfect matching polytopes of two fundamentalgraphclasses,namelynear-bricksandbicriticalgraphs,arebox-totallydualintegral. We discuss implications of these results for identifying perfect matching polytopes with the integer decomposition property. This in particular unveils a new positive case of the generalized Berge-Fulkeron conjecture.
- Affiliations
Citations
Grappe, R., Lacroix, M., & Pisanu, F. (2024). On strong integrality properties of the perfect matching polytope (LIDAM Discussion Paper CORE 2024/32). https://hdl.handle.net/2078.5/248281