Parameterized algorithm for 3-path vertex cover

2018/09/07 by Tsur, Dekel · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1809.02636

Abstract

In the 3-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 3 vertices in G contains at least one vertex of S. In this paper we give parameterized algorithm for 3-path cover whose time complexity is O^*(1.713^k). Our algorithm is faster than previous algorithms for this problem.

Cited by

• Sharp lower bounds and extremal graphs for the generalized k-independence number
• A sharp lower bound on the generalized 4-independence number

Related

• An O^*(2.619^k) algorithm for 4-path vertex cover
• l-path vertex cover is easier than l-hitting set for small l
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• Weighted vertex cover on graphs with maximum degree 3
• A Survey on the k-Path Vertex Cover Problem