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

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)
    45 Downloads (Pure)


    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.

    Original languageEnglish
    Pages (from-to)1061-1094
    Number of pages34
    JournalSIAM journal on discrete mathematics
    Issue number2
    Publication statusPublished - 27 Jun 2019


    • quadratic matching problem
    • matching polytope
    • bipartite matching

    Cite this