Exponential running time of simple_cycles with length_bound (_bounded_cycle_search)

Follow-up to #8265

Current Behavior

I execute

import sys
print(sys.version)

import time

import networkx as nx
print(nx.__version__)

def diamond_chain(t):
    G = nx.DiGraph()
    for i in range(t):
        G.add_edges_from([(f"d{i}", f"a{i}"), (f"d{i}", f"b{i}"),
                          (f"a{i}", f"d{i+1}"), (f"b{i}", f"d{i+1}")])
    G.add_edge(f"d{t}", "d0")     # every cycle has length 2t+1
    return G                      # run with length_bound = 2*t  →  c = 0

for t in range(10, 30):
    G = diamond_chain(t)
    n = G.number_of_nodes()
    m = G.number_of_edges()
    s = "d0"
    k = 2*t
    tick = time.process_time()
    cycles = list(nx.simple_cycles(G, k))
    tock = time.process_time()
    print(f"{t=:2} {n=:2} {m=:3} {k=:2} {cycles=} {tock-tick=:6.2f}")

and get the following output:

3.14.5 (tags/v3.14.5:5607950, May 10 2026, 10:43:50) [MSC v.1944 64 bit (AMD64)]
3.6.1
t=10 n=31 m=41 k= 20 cycles=[] tock-tick=  0.00
t=11 n=34 m=45 k= 22 cycles=[] tock-tick=  0.00
t=12 n=37 m=49 k= 24 cycles=[] tock-tick=  0.00
t=13 n=40 m=53 k= 26 cycles=[] tock-tick=  0.02
t=14 n=43 m=57 k= 28 cycles=[] tock-tick=  0.00
t=15 n=46 m=61 k= 30 cycles=[] tock-tick=  0.03
t=16 n=49 m=65 k= 32 cycles=[] tock-tick=  0.06
t=17 n=52 m=69 k= 34 cycles=[] tock-tick=  0.09
t=18 n=55 m=73 k= 36 cycles=[] tock-tick=  0.17
t=19 n=58 m=77 k= 38 cycles=[] tock-tick=  0.41
t=20 n=61 m=81 k= 40 cycles=[] tock-tick=  0.81
t=21 n=64 m=85 k= 42 cycles=[] tock-tick=  1.61
t=22 n=67 m=89 k= 44 cycles=[] tock-tick=  3.27
t=23 n=70 m=93 k= 46 cycles=[] tock-tick=  6.47
t=24 n=73 m=97 k= 48 cycles=[] tock-tick= 12.92
t=25 n=76 m=101 k=50 cycles=[] tock-tick= 25.88
t=26 n=79 m=105 k=52 cycles=[] tock-tick= 53.34
t=27 n=82 m=109 k=54 cycles=[] tock-tick=105.56
t=28 n=85 m=113 k=56 cycles=[] tock-tick=212.06
t=29 n=88 m=117 k=58 cycles=[] tock-tick=420.64

The time spent roughly doubles for each increment of t: ... 0.41 → 0.81 → 1.61 → 3.27 → 6.47 → 12.92 ... Your timing may vary, but you will observe a similar exponential growth.

A similar exponential growth will also be observed when replacing simple_cycles by the inner loop, enumerating all length k bound cycles containing node s:

cycles = list(nx.algorithms.cycles._bounded_cycle_search(G, [s], k))

Expected Behavior

The graph contains exactly 2^t simple cycles, all of the length 2t+1 > k, so the search must terminate without output; total time = one delay period.

The graphs are sparse, n=3t+1, m= 4t+1, k=2t and the delay for _bounded_cycle_search should be at most quadratic in t.

For graphs that small and without an excessive number of valid cycles, the observed delay should stay close to zero.

Steps to Reproduce

Run the code snippet. If necessary, adapt the range of t to your machine.

Environment

• Win11
• Python version: 3.14.5
• NetworkX version: 3.6.1

Additional context

nx.simple_cycles uses networkx.algorithms.cycles._bounded_cycle_search internally which claims to implement "The main loop of the cycle-enumeration algorithm of Gupta and Suzumura." (https://github.com/networkx/networkx/blob/main/networkx/algorithms/cycles.py)

In https://arxiv.org/abs/2105.10094v2, Gupta and Suzumura claim for that main loop (CYCLE_SEARCH): "Therefore, the time associated with finding a valid cycle cannot exceed O((k−1)(|Vs|+|Es|)), and the time complexity of CYCLE_SEARCH for finding all valid cycles in a given subgraph Gs is O((cs+1)(k−1)(|Vs|+|Es|)), where cs is the number of valid cycles in which the smallest vertex is s."

Recently https://arxiv.org/abs/2512.08392v3, Bauernöppel and Sack

1. demonstrate that CYCLE_SEARCH fails to enumerate certain valid cycles,
2. demonstrate that there is a gap in the CYCLE_SEARCH delay bound proof, and
3. propose SimpleSearch as a replacement, proving its completeness and O(k(n+m)) delay.

Disclosure: I am the first author.

Core Findings

_bounded_cycle_search is not a faithful transcription of the cited pseudocode:

1. The assignment lock[w] = len(path) is executed after the append, one off from the pseudocode's Lock(v) = flen: re-entry is admitted at equal depth where the pseudocode requires strictly shallower.
2. The blen aggregation is missing the increment min(blen[-1], bl) instead of min(blen[-1], 1 + bl), reducing blen to a boolean found-flag as in Johnson's algorithm.

The first deviation alone produces this family's blowup (with no cycles output, no relaxation ever fires, so the second deviation is not exercised).

Patching 1. alone would improve the timing here, but we have found another, more complex graph family (available on request) failing the O(k(n+m)) delay bound even with 1. patched.

Patching 1. + 2. would restore the original CYCLE_SEARCH algorithm, including its issues.

Neither is a viable option.

SimpleSearch

SimpleSearch is a depth-k limited depth-first search. Before recursion, the fruitful (output producing) successors of the current node are filtered by a reachability test in the reverse graph, implemented as a breadth-first search.

from collections import deque

def simple_search(G, s, k):
    """Enumerate all simple cycles in G of bounded length k containing node s."""

    def reach(blocked, successors, budget):
        reached = {s}
        queue = deque()
        queue.append((s, 0))
        while queue:
            (u, d) = queue.popleft()
            if d >= budget:
                break
            for v in G.predecessors(u):
                if v not in blocked and v not in reached:
                    reached.add(v)
                    queue.append((v, d + 1))

        fruitful = [w for w in successors if w in reached]
        return fruitful

    def search(path, v, budget):
        path.append(v)
        fruitful = reach(set(path), G.successors(v), budget - 1)
        for w in fruitful:
            if w == s:
                yield path[:]   # output cycle
            else:
                yield from search(path, w, budget - 1)
        path.pop()

    path = list()
    yield from search(path, s, k)

Using SimpleSearch, the execution is instant. In fact, timing is dominated by graph generation. I had to use for t in range(100_000, 300_000, 10_000): to get some non-zero timing output.

If you are interested, I will help to optimize and integrate SimpleSearch, including thorough timing experiments.