Efficient algorithm for the vertex cover Pk problem on cacti

摘要

Given a graph G=(V,E), the vertex cover Pk (VCPk) problem is to find a minimum set F⊆V such that every path of order k in G contains at least one vertex from F. For any integer k ≥ 2, the VCPk problem for general graphs is NP-hard. The paper presents an efficient algorithm for the VCPk problem on cacti.