On strong integrality properties of the perfect matching polytope

Roland Grappe, Mathieu Lacroix and Francesco Pisanu ()
Additional contact information
Roland Grappe: Université Paris Dauphine
Mathieu Lacroix: Université Sorbonne Paris Nord
Francesco Pisanu: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2024032, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Perfect matching polytope; Box-totally dual integral polyhedron; Integer decomposition property (search for similar items in EconPapers)
Pages: 20
Date: 2024-12-17
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2024032

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().