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 k -vertex cover polytope (the convex hull of vertex covers of size k ). Our main result is that there are extended formulations of size O ( 1.4 7 k + k n ) . We also provide FPT extended formulations for solutions of size k to instances of d -hitting set.