A search for faster algorithms for the capacitated vertex cover problem

Abstract

The vertex cover problem is a well studied problem. A natural extension to the vertex cover problem is the capacitated vertex cover problem (CVC). In this problem each vertex has a predefined capacity which indicates the total amount of edges that vertex can cover, if the vertex is included in the cover. The CVC problem can be solved trivially in O^*(2^n) time by enumerating all possible covers. For the CVC problem there is no known exact exponential algorithm which solves the problem in O^*(c^n) time for some constant c < 2.

In this thesis we study the CVC problem and search for faster algorithms which solve the capacitated vertex cover problem on specific graph classes. We show the complexity of the problem with several NP-completeness proofs of the CVC problem on bipartite graphs. We will show a linear time algorithm for the CVC problem on trees and show a path- and treewidth algorithm. We will also study exponential algorithms which solve the CVC problem in O^*(c^n) time on some specific graphs classes, for some constant c < 2. The general case of the CVC problem in O^*(c^n) time will be discussed and we give some results on the difficulty of the problem with respect to the Strong Exponential Time Hypothesis.