# 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.

Scroll to Top