A Decentralized Strategy for Unweighted Minimum Vertex Cover

The minimum vertex cover is a classical, NP-hard, optimization problem whose objective, given a graph, is to identify the smallest subset of vertices that covers all edges. This paper introduces a decentralized, iterative, and message-passing algorithm that leverages the local knowledge of nodes to resolve the minimum vertex cover. Due to its convergence speed and minimal computational footprint, it also performed well as an in-memory sequential solver, achieving results comparable to those obtained from a state-of-the-art centralized approach.