2022/01/10 by Jianhua Tu, Tu, Jianhua
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2201.03397
Given a graph G=(V,E) and a positive integer k≥2, a k-path vertex cover is a subset of vertices F such that every path on k vertices in G contains at least one vertex from F. A minimum k-path vertex cover in G is a k-path vertex cover with minimum cardinality and its cardinality is called the \it k-path vertex cover number of G. In the \it k-path vertex cover problem, it is required to find a minimum k-path vertex cover in a given graph. In this paper, we present a brief survey of the current state of the art in the study of the k-path vertex cover problem and the k-path vertex cover number.