2015/09/18 by Yohann Benchetrit, Benchetrit, Yohann, András Sebő +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #graph theory and CDMA systems #math.CO #math.OC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.05586
arxiv created 2015/09/18 · openalex publication_date 2015/09/18 · arxiv updated 2015/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The complexity of the matching polytope of graphs may be measured with the maximum length β of a starting sequence of odd ears in an ear-decomposition. Indeed, a theorem of Edmonds and Pulleyblank shows that its facets are defined by 2-connected factor-critical graphs, which have an odd ear-decomposition (according to a theorem of Lovász). In particular, β(G) ≤ 1 if and only if the matching polytope of the graph G is completely described by non-negativity, star and odd-circuit inequalities. This is essentially equivalent to the h-perfection of the line-graph of G, as observed by Cao and Nemhauser. The complexity of computing β is apparently not known. We show that deciding whether β(G)≤ 1 can be executed efficiently by looking at any ear-decomposition starting with an odd circuit and performing basic modulo-2 computations. Such a greedy-approach is surprising in view of the complexity of the problem in more special cases by Bruhn and Schaudt, and it is simpler than using the Parity Minor Algorithm. Our results imply a simple polynomial-time algorithm testing h-perfection in line-graphs (deciding h-perfection is open in general). We also generalize our approach to binary matroids and show that computing β is a Fixed-Parameter-Tractable problem (FPT).