Journal article
Polynomial size linear programs for problems in P
Abstract
A perfect matching in an undirected graph G = ( V , E ) is a set of vertex disjoint edges from E that include all vertices in V . The perfect matching problem is to decide if G has such a matching. Recently Rothvoß proved the striking result that the Edmonds’ matching polytope has exponential extension complexity. In this paper for each n = | V | we describe a polytope for the perfect matching problem that is different from Edmonds’ polytope …
Authors
Avis D; Bremner D; Tiwary HR; Watanabe O
Journal
Discrete Applied Mathematics, Vol. 265, , pp. 22–39
Publisher
Elsevier
Publication Date
July 2019
DOI
10.1016/j.dam.2019.03.016
ISSN
0166-218X