manuel di lullo https github commanueldilullo description approximization algorithm for minimum vertex cover problem matching approach uses graphs represented with an adjacency list url https mathworld wolfram comminimumvertexcover html url https www princeton eduaaapublicteachingorf523orf523lec6 pdf apx algorithm for min vertex cover using matching approach input graph graph stored in an adjacency list where each vertex is represented as an integer example graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 matchingminvertexcovergraph 0 1 2 4 chosenvertices set of chosen vertices edges list of graph s edges while there are still elements in edges list take an arbitrary edge fromnode tonode and add his extremity to chosenvertices and then remove all arcs adjacent to the fromnode and tonode return a set of couples that represents all of the edges input graph graph stored in an adjacency list where each vertex is represented as an integer example graph 0 1 3 1 0 3 2 0 3 3 0 1 2 getedgesgraph 0 1 3 1 0 3 2 0 3 0 2 3 1 0 3 2 1 3 graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 printfmatching vertex cover nmatchingminvertexcovergraph apx algorithm for min vertex cover using matching approach input graph graph stored in an adjacency list where each vertex is represented as an integer example graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 matching_min_vertex_cover graph 0 1 2 4 chosen_vertices set of chosen vertices edges list of graph s edges while there are still elements in edges list take an arbitrary edge from_node to_node and add his extremity to chosen_vertices and then remove all arcs adjacent to the from_node and to_node return a set of couples that represents all of the edges input graph graph stored in an adjacency list where each vertex is represented as an integer example graph 0 1 3 1 0 3 2 0 3 3 0 1 2 get_edges graph 0 1 3 1 0 3 2 0 3 0 2 3 1 0 3 2 1 3 graph 0 1 3 1 0 3 2 0 3 4 3 0 1 2 4 2 3 print f matching vertex cover n matching_min_vertex_cover graph
def matching_min_vertex_cover(graph: dict) -> set:
    
    
    chosen_vertices = set()
    
    edges = get_edges(graph)

    
    
    
    while edges:
        from_node, to_node = edges.pop()
        chosen_vertices.add(from_node)
        chosen_vertices.add(to_node)
        for edge in edges.copy():
            if from_node in edge or to_node in edge:
                edges.discard(edge)
    return chosen_vertices


def get_edges(graph: dict) -> set:
    
    edges = set()
    for from_node, to_nodes in graph.items():
        for to_node in to_nodes:
            edges.add((from_node, to_node))
    return edges


if __name__ == "__main__":
    import doctest

    doctest.testmod()