Shi-Qin Li

A hybrid algorithm for the minimum weight 4-path vertex cover problem

The minimum weight k-path vertex cover problem is defined on a vertex-weighted graph G, where the objective is to find a vertex subset S such that every path of order k contains at least one vertex in S, while minimizing the total weight of S. For any integer k ≥ 2, this problem is NP-hard on general graphs. In this st...