Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142144 | Operations Research Letters | 2016 | 5 Pages |
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
Austin Buchanan,