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

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)
    29 Downloads (Pure)

    Abstract

    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
    Volume33
    Issue number2
    DOIs
    Publication statusPublished - 27 Jun 2019

    Keywords

    • quadratic matching problem
    • matching polytope
    • bipartite matching

    Cite this