TryAlgo

Shortest cycle

Find a shortest cycle in a given undirected graph.

Algorithm in time \(O(|V|\cdot |E|)\) using BFS

The BFS graph traversal can be used for this purpose. Here is a discussion why DFS cannot help for this problem.

The key observation is the following. Suppose you start a BFS exploration at some root vertex \(r\). The exploration places the vertices into levels according to the distance from the root, where the root is in level 0. The BFS exploration distinguishes between different kind of edges. First there are the forward edges which lead to unmarked vertices. These edges form the BFS tree. The remaining edges form cycles with the tree, and are called traversal edges. These edges can only connect vertices from the same level or from adjacent levels.

If from a vertex \(u\) at level \(i\) we discover a traversal edge to a neighbor \(v\) at level \(j\) then we know that there is a cycle consisting of the path from \(r\) to \(u\) in the BFS tree, the edge \((u,v)\) and the path from \(v\) to \(r\) in the BFS tree. This cycle has length \(i+1+j\). Also the cycle is simple if and only if \(r\) is the lowest common ancestor of \(u\) and \(v\) on the BFS tree. Otherwise we know that there is a simple cycle of length at most \(i+j\).

Hence in order to find a shortest cycle simply loop over all possible root vertices \(r\). Initiate a BFS search at \(r\), and for every non-forward edge \(u,v\) you encounter, keep track of the tree vertices \(r,u,v\) that minimize the sum of the levels of \(u\) and of \(v\). After that you know that for the minimizers \(r,u,v\), there is a shortest cycle containing these vertices. Then you just need a last BFS search initiated at \(r\), or alternatively you can store with the minimizers \(r,u,v\) the correspondonding BFS tree. From that tree you obtain the shortest path from \(r\) to \(u\) and to \(v\). Together with the edge \((u,v)\) they form a shortest cycle.

Pruning

Once you have discovered a cycle of length k you can prune the tree at the level k/2, meaning that you don’t need to explore below that level because you won’t discover shorter cycles then.

def bfs(graph, root, prune_level):
    """make a pruned BFS search of the graph starting at root.
    returns the BFS tree, and possibly a traversal edge (u,v) that with the tree
    forms a cycle of some length.
    Complexity: O(V + E)
    """
    n = len(graph)
    level = [-1] * n                      # -1 == not seen
    tree = [None] * n                     # pointers to predecessors
    toVisit = deque([root])               # queue for BFS
    level[root] = 0
    tree[root] = root
    best_cycle = float('inf')             # start with infinity
    best_u = None
    best_v = None
    while toVisit:
        u = toVisit.popleft()
        if level[u] > prune_level:
            break
        for v in graph[u]:
            if tree[u] == v:              # ignore the tree edge
                continue
            if level[v] == -1:            # new vertex - tree edge
                level[v] = level[u] + 1
                toVisit.append(v)
                tree[v] = u
            else:                         # vertex already seen - traversal edge
                prune_level = level[v] - 1
                cycle_len = level[u] + 1 + level[v]
                if cycle_len < best_cycle:  # footnote (1)
                    best_cycle = cycle_len
                    best_u = u
                    best_v = v
    return tree, best_cycle, best_u, best_v


def path(tree, v):
    """returns the path in the tree from v to the root
    Complexity: O(V)
    """
    P = []
    while not P or P[-1] != v:
        P.append(v)
        v = tree[v]
    return P


def shortest_cycle(graph):
    """Returns a shortest cycle if there is any
    Complexity: O(V * (V + E))
    """
    best_cycle = float('inf')
    best_u = None
    best_v = None
    best_tree = None
    V = list(range(len(graph)))
    for root in V:
        tree, cycle_len, u, v = bfs(graph, root, best_cycle // 2)
        if cycle_len < best_cycle:
            best_cycle = cycle_len
            best_u = u
            best_v = v
            best_tree = tree
    if best_cycle == float('inf'):
        return None                   # no cycle found
    Pu = path(best_tree, best_u)
    Pv = path(best_tree, best_v)
    return Pu[::-1] + Pv              # combine path to make a cycle