Approximation Algorithms

def vertex_cover_approx(graph):
    """2-approximation for Vertex Cover"""
    cover = set()
    edges = list(graph.edges())
    
    while edges:
        u, v = edges[0]
        cover.add(u)
        cover.add(v)
        # Remove all edges incident to u or v
        edges = [(x, y) for x, y in edges if x not in {u, v} and y not in {u, v}]
    
    return cover

def set_cover_approx(universe, sets):
    """Greedy approximation for Set Cover"""
    covered = set()
    cover = []
    
    while covered < universe:
        # Select set covering most uncovered elements
        best_set = max(sets, key=lambda s: len(s - covered))
        cover.append(best_set)
        covered |= best_set
    
    return cover