Charles Explorer logo
🇬🇧

Polynomial size linear programs for problems in P

Publication at Faculty of Mathematics and Physics |
2019

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 Rothvoss proved the striking result that the Edmonds' matching polytope has exponential extension complexity. In this paper for each n = vertical bar V vertical bar we describe a polytope for the perfect matching problem 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.

With this construction, a straightforward O(n(4)) implementation of Edmonds' matching algorithm using O(n(2)) bits of space would yield a WEF Q with O(n(6) log n) inequalities and variables. 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 polynomial 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 the 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 P which can be solved by a well defined 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 P/POLY. (C) 2019 Elsevier B.V.

All rights reserved.