TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree

Abstract

In this report we describe a new approach to improve algorithms for solving the k-Vertex Cover problem. The algorithm uses graph cutting, during the tree search phase, as a basis for identifying, disconnecting, and processing small fractions of the residual graph. Unlike previous methods that use separator theorems constrained to restricted graph classes and requiring complex dynamic programming, this algorithm applies to graphs of small, bounded degree, uses existing branching rules and incurs no any additional complexity.Such graph instances are generated during the tree search phases of the current best FPT k-vertex cover algorithms. Any future advances in sequential algorithms for the k-Vertex Cover problem can incorporate this approach, thus improving their complexity.