Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover

09/10/2022
by   Nate Veldt, et al.
0

This paper presents a fast and simple new 2-approximation algorithm for minimum weighted vertex cover. The unweighted version of this algorithm is equivalent to a well-known greedy maximal independent set algorithm. We prove that this independent set algorithm produces a 2-approximate vertex cover, and we provide a principled new way to generalize it to node-weighted graphs. Our analysis is inspired by connections to a clustering objective called correlation clustering. To demonstrate the relationship between these problems, we show how a simple Pivot algorithm for correlation clustering implicitly approximates a special type of hypergraph vertex cover problem. Finally, we use implicit implementations of this maximal independent set algorithm to develop fast and simple 2-approximation algorithms for certain edge-deletion problems that can be reduced to vertex cover in an approximation preserving way.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset