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. While the polyhedral approximability of vertex cover has been studied, we know of no extended formulations parameterized by the size of the vertex cover. To this end, we study the k-vertex cover polytope, which is the convex hull of vertex covers of size k. Our main result is that there are extended formulations of size O(1.47^k+ kn). We also provide FPT extended formulations for solutions of size k to instances of d-hitting set.
Citation
In Press at Operations Research Letters doi:10.1016/j.orl.2016.03.008 http://www.sciencedirect.com/science/article/pii/S0167637716000481 Preprint available on personal webpage: https://sites.google.com/site/austinlbuchanan/home/research