Minimum k-path vertex cover

Abstract

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψ_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining ψ_k(G) is NP-hard for each k \geq 2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψ_k(G) and provide several estimations and exact values of ψ_k(G). We also prove that ψ_3(G) \leq (2n + m)/6, for every graph G with n vertices and m edges.

submitted manuscript

References in corpus (1)

• Finding paths of length k in O*(2^k) time

Cited by in corpus (16)

• Storage Capacity of Repairable Networks
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
• Approximation Algorithm for N-distance Minimal Vertex Cover Problem
• K-Reach: Who is in Your Small World
• Improved approximation algorithms for path vertex covers in regular graphs
• On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling
• Approximation algorithms for hitting subgraphs
• TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k\ge 4$
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• The k-path vertex cover: general bounds and chordal graphs
• On the dissociation number of Kneser graphs
• On path sequences of graphs
• Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs
• The maximum number of maximum dissociation sets in trees