A Decentralized Strategy for Unweighted Minimum Vertex Cover
Matteo Mordacchini, Emanuele Carlini, Patrizio Dazzi · 2025
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.