An O^*(2.619^k) algorithm for 4-path vertex cover

2018/11/08 by Dekel Tsur, Tsur, Dekel · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1811.03592

Abstract

In the 4-path vertex cover problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-path vertex cover whose time complexity is O^*(2.619^k).

Cited by

• l-path vertex cover is easier than l-hitting set for small l

Related

• Parameterized algorithm for 3-path vertex cover
• An Approximation Algorithm for Covering Vertices by 4⁺-Paths
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• l-path vertex cover is easier than l-hitting set for small l
• A Survey on the k-Path Vertex Cover Problem