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

2019/06/22 by Dekel Tsur, Tsur, Dekel
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.1906.10523

openalex publication_date 2019/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the l-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 G-S does not contain a path with l vertices. In this paper we give parameterized algorithms for l-path vertex cover for l = 5,6,7, whose time complexities are O^*(3.945^k), O^*(4.947^k), and O^*(5.951^k), respectively.

Citations

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

Related

• Parameterized algorithm for 3-path vertex cover
• An O^*(2.619^k) algorithm for 4-path vertex cover
• A Survey on the k-Path Vertex Cover Problem
• Generating faster algorithms for d-Path Vertex Cover
• Vertex Cover Gets Faster and Harder on Low Degree Graphs