Above guarantee parameterization for vertex cover on graphs with maximum degree 4

2018/12/27 by Tsur, Dekel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1812.10808

Abstract

In the vertex cover problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of vertices S of size at most k such that every edge of G is incident on at least one vertex in S. We study the vertex cover problem on graphs with maximum degree 4 and minimum degree at least 2, parameterized by r = k-n/3. We give an algorithm for this problem whose running time is O^*(1.6253^r). As a corollary, we obtain an O^*(1.2403^k)-time algorithm for vertex cover on graphs with maximum degree 4.

Related

• Weighted vertex cover on graphs with maximum degree 3
• An O^*(2.619^k) algorithm for 4-path vertex cover
• Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
• A faster algorithm for Vertex Cover parameterized by solution size
• Parameterized algorithm for 3-path vertex cover