Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs

We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended by a binary entry indicating whether the matching contains two specific edges. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. In addition, we also derive facetness and separation results for the polytopes. The completeness proof is based on a geometric relationship to a matching polytope of a nonbipartite graph. Using standard techniques, we finally extend the result to capacitated b-matchings.