Comparative Analysis of Greedy Algorithms for Minimum Vertex Cover in Unit Disk Graphs

The Minimum Vertex Cover (MVC) problem is NP-hard even on unit disk graphs (UDGs), which model wireless sensor networks and other geometric systems. This paper presents an experimental comparison of three greedy algorithms for MVC on UDGs: degree-based greedy, edge-based greedy, and the classical 2-approximation based on maximal matching. Our evaluation on randomly generated UDGs with up to 500 vertices shows that the degree-based heuristic achieves approximation ratios between 1.636 and 1.968 relative to the maximal matching lower bound, often outperforming the theoretical 2-approximation bound in practice. However, it provides no worst-case guarantee. In contrast, the matching-based algorithm consistently achieves the proven 2-approximation ratio while offering superior running times (under 11 ms for graphs with 500 vertices). The edge-based heuristic demonstrates nearly identical performance to the degree-based approach. These findings highlight the practical trade-off between solution quality guarantees and empirical performance in geometric graph algorithms, with the matching-based algorithm emerging as the recommended choice for applications requiring reliable worst-case bounds.