manuel di lullo https github commanueldilullo description approximization algorithm for minimum vertex cover problem greedy approach uses graphs represented with an adjacency list url https mathworld wolfram comminimumvertexcover html url https cs stackexchange comquestions129017greedyalgorithmforvertexcover greedy apx algorithm for min vertex cover input graph graph stored in an adjacency list where each vertex is represented with an integer example graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 greedyminvertexcovergraph 0 1 2 4 queue used to store nodes and their rank for each node and his adjacency list add them and the rank of the node to queue using heapq module the queue will be filled like a priority queue heapq works with a min priority queue so i used 1lenv to build it ologn chosenvertices set of chosen vertices while queue isn t empty and there are still edges queue00 is the rank of the node with max rank extract vertex with max rank from queue and add it to chosenvertices remove all arcs adjacent to argmax if v haven t adjacent node skip if argmax is reachable from elem remove argmax from elem s adjacent list and update his rank reorder the queue greedy apx algorithm for min vertex cover input graph graph stored in an adjacency list where each vertex is represented with an integer example graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 greedy_min_vertex_cover graph 0 1 2 4 queue used to store nodes and their rank for each node and his adjacency list add them and the rank of the node to queue using heapq module the queue will be filled like a priority queue heapq works with a min priority queue so i used 1 len v to build it o log n chosen_vertices set of chosen vertices while queue isn t empty and there are still edges queue 0 0 is the rank of the node with max rank extract vertex with max rank from queue and add it to chosen_vertices remove all arcs adjacent to argmax if v haven t adjacent node skip if argmax is reachable from elem remove argmax from elem s adjacent list and update his rank re order the queue
import heapq


def greedy_min_vertex_cover(graph: dict) -> set[int]:
    
    
    queue: list[list] = []

    
    
    
    for key, value in graph.items():
        
        heapq.heappush(queue, [-1 * len(value), (key, value)])

    
    chosen_vertices = set()

    
    
    while queue and queue[0][0] != 0:
        
        argmax = heapq.heappop(queue)[1][0]
        chosen_vertices.add(argmax)

        
        for elem in queue:
            
            if elem[0] == 0:
                continue
            
            
            if argmax in elem[1][1]:
                index = elem[1][1].index(argmax)
                del elem[1][1][index]
                elem[0] += 1
        
        heapq.heapify(queue)
    return chosen_vertices


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    graph = {0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]}
    print(f"Minimum vertex cover:\n{greedy_min_vertex_cover(graph)}")