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

Abstract

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 study, we focused on the case k = 4. We propose a hybrid framework that integrates a deep Q-network with a local search algorithm. Experimental results on randomly generated instances demonstrate that our method outperforms baseline algorithms and exhibits strong generalization.