Optimization Online


Extended Formulations for Vertex Cover

Austin Buchanan (buchanan***at***okstate.edu)

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. 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.

Keywords: fixed-parameter tractable; extended formulation; vertex cover; independent set; cardinality constrained; hitting set; hypergraph

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming

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


Entry Submitted: 10/04/2015
Entry Accepted: 10/05/2015
Entry Last Modified: 03/21/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society