Extended formulations for vertex cover

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.