what are good algorithms for removing the edges of a graph that are not part of at least one cycle?

We can get a linear-time algorithm by modifying the algorithm due to Hopcroft and Tarjan for finding articulation points.

First, a little bit of theory: for all spanning trees T, for all edges e, there exists a cycle containing e if and only if there exists a fundamental cycle with respect to T that contains e. The particular choice of T in the algorithm is a depth-first search tree, which helpfully has only tree and back edges.

The high-level idea behind the code below is, whenever we find a back edge, mark the edges comprising the fundamental cycle as belonging to a cycle. Naively, this yields a quadratic-time algorithm, so what we do instead is have each recursive call return the minimum depth reachable by tree edges followed by a back edge, which we compare against the current vertex’s depth to determine whether the edge just traversed is marked.

In Python 3:

graph = {
    1: {2, 3},
    2: {1, 4},
    3: {1, 4},
    4: {2, 3, 5},
    5: {4, 6},
    6: {5, 7},
    7: {6, 8, 9, 13},
    8: {7},
    9: {7, 10, 11},
    10: {9, 11},
    11: {9, 10, 12},
    12: {11, 13},
    13: {7, 12, 14},
    14: {13},
}

for v, neigh in graph.items():
    for w in neigh:
        assert v in graph[w]

depths = {}


def traverse(v, depth, parent):
    if v in depths:
        return depths[v]
    depths[v] = depth
    v_low = float("inf")
    for w in graph[v]:
        if w == parent:
            continue
        w_low = traverse(w, depth + 1, v)
        if w_low <= depth:
            print(v, "--", w)
        v_low = min(v_low, w_low)
    return v_low


print("graph {")
for v in graph.keys():
    traverse(v, 0, None)
print("}")

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top