Article ID Journal Published Year Pages File Type
1142144 Operations Research Letters 2016 5 Pages PDF
Abstract

The vertex cover polytopes of graphs do not admit polynomial-size extended formulations. This motivates the search for polyhedral analogues to approximation algorithms and fixed-parameter tractable (FPT) algorithms. In this paper, we take the FPT approach and study the kk-vertex cover polytope (the convex hull of vertex covers of size kk). Our main result is that there are extended formulations of size O(1.47k+kn)O(1.47k+kn). We also provide FPT extended formulations for solutions of size kk to instances of dd-hitting set.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,