Polynomial size linear programs for problems in P
Preprint
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{\ss} proved the striking result that the Edmonds' matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds' polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {\bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {\bf P/Poly}.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Compact linear programs for 2SATEuropean Journal of Combinatorics, 2019
- The Matching Polytope has Exponential Extension ComplexityJournal of the ACM, 2017
- A generalization of extension complexity that captures PInformation Processing Letters, 2015
- Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM, 2015
- On the extension complexity of combinatorial polytopesMathematical Programming, 2014
- On the geometric interpretation of the nonnegative rankLinear Algebra and its Applications, 2012
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Linear programming is log-space hard for PInformation Processing Letters, 1979
- An O (N2.5) algorithm for maximum matching in general graphs1975
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965