A generalization of extension complexity that captures $P$
Preprint
Abstract
In this paper we propose a generalization of the extension complexity of a polyhedron $Q$. On the one hand it is general enough so that all problems in $P$ can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for $NP$-hard problems independently of whether or not $P=NP$. The generalization, called $H$-free extension complexity, allows for a set of valid inequalities $H$ to be excluded in computing the extension complexity of $Q$. We give results on the $H$-free extension complexity of hard matching problems (when $H$ are the odd set inequalities) and the traveling salesman problem (when $H$ are the subtour elimination constraints).
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Partitioning to three matchings of given size is NP-complete for bipartite graphsActa Universitatis Sapientiae, Informatica, 2014
- On the Extension Complexity of Combinatorial PolytopesLecture Notes in Computer Science, 2013
- Extended Formulations, Nonnegative Factorizations, and Randomized Communication ProtocolsLecture Notes in Computer Science, 2012
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Using separation algorithms to generate mixed integer model reformulationsOperations Research Letters, 1991
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization ProblemsSIAM Journal on Algebraic Discrete Methods, 1985
- NP-completeness of some generalizations of the maximum matching problemInformation Processing Letters, 1982
- Edge Dominating Sets in GraphsSIAM Journal on Applied Mathematics, 1980
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965