On a class of strong valid inequalities for the connected matching polytope

2023/09/25 by Phillippe Samer, Samer, Phillippe
Computer Science · Engineering · Mathematics · #90C27 (Secondary) #90C57 (Primary) 52B05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2309.14019

openalex publication_date 2023/09/25 · openalex created_date 2023/09/27 · openalex updated_date 2026/07/28

Abstract

We identify a family of O(|E(G)|²) nontrivial facets of the connected matching polytope of a graph G, that is, the convex hull of incidence vectors of matchings in G whose covered vertices induce a connected subgraph. Accompanying software to further inspect the polytope of an input graph is available.

Related

• Complete Description of Matching Polytopes with One Linearized Quadratic\n Term for Bipartite Graphs
• Two-edge-connected (not necessarily spanning) subgraphs and polyhedra
• On the vertex degrees of the skeleton of the matching polytope of a graph
• Facets of the (s,t)-p-path polytope
• The Total Matching Polytope of Complete Bipartite Graphs