Cactus Graphs, in depth: edge versus vertex cacti, linear-time recognition, spanning-tree counts and independent set DP

Definitions: edge cacti, vertex cacti and blocks

There are two definitions in the literature, and mixing them up is the most common mistake. An edge cactus (the usual meaning, and the one used here) is a connected graph in which every edge belongs to at most one simple cycle. A vertex cactus is stricter: every vertex belongs to at most one simple cycle. Two triangles sharing one vertex form an edge cactus but not a vertex cactus. Check which definition a problem statement uses before you pick an algorithm.

The cleanest characterisation uses blocks. A block, or biconnected component, is a maximal subgraph with no articulation point; every edge belongs to exactly one block. A connected graph is an edge cactus exactly when every block is either a single edge (a bridge) or a simple cycle. That lets you reuse block decomposition machinery from articulation points, and it gives the block-cut tree: one node per block, one node per articulation point, edges for membership. For a cactus, that tree is the skeleton every algorithm walks.

Structural facts that make cacti easy

Four facts carry most of the algorithms.

1. Edge count. A spanning tree has n - 1 edges, and each cycle adds exactly one more edge, so m = n - 1 + c, where c is the number of cycles. Cycles are edge-disjoint and each has at least 3 edges, so 3c <= m. Substituting gives c <= (n - 1) / 2 and m <= floor(3(n - 1) / 2). A cactus is sparse, and any input with more edges can be rejected immediately.
2. Spanning trees. A spanning tree must keep every bridge and drop exactly one edge from each cycle, independently. The number of spanning trees is the product of the cycle lengths. General graphs need a determinant for this.
3. Treewidth at most 2. Cacti contain no K4 minor, so every NP-hard problem that is easy on bounded treewidth is polynomial on a cactus. Cacti are also outerplanar.
4. Distances. Inside one cycle of length L, the distance between two vertices k steps apart along the cycle is min(k, L - k). Between blocks, the route is fixed by the block-cut tree, so shortest paths are unique up to the choice of direction around each cycle.

Recognition with one depth-first search

Recognition is one depth-first search. Every non-tree edge in an undirected DFS joins a vertex to one of its ancestors, and together with the tree path between them it forms a cycle. Walk that tree path when the back edge is found and mark each tree edge. If a tree edge is already marked, two cycles share it and the graph is not a cactus. Each tree edge is marked at most once before the algorithm either finishes or stops, so the whole test runs in O(n + m). The same pass records each cycle as a vertex list ending at its top vertex, the ancestor end of the back edge, which the dynamic program below uses. See BFS and DFS for the traversal itself. The code is iterative, so deep graphs do not hit Python's recursion limit.

def decompose(n, edges):
    """Return (parent, order, cycles, bridge_child) for an edge cactus, else None.
    Each cycle is [x, parent(x), ..., top]; the back edge is x -> top."""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i)); adj[v].append((u, i))
    parent, pedge, depth = [-1] * n, [-1] * n, [-1] * n
    on_cycle = [False] * len(edges)
    cycles, order = [], [0]
    depth[0] = 0
    stack = [(0, iter(adj[0]))]
    while stack:
        u, it = stack[-1]
        for v, ei in it:
            if ei == pedge[u]:
                continue
            if depth[v] == -1:                       # tree edge
                parent[v], pedge[v], depth[v] = u, ei, depth[u] + 1
                order.append(v)
                stack.append((v, iter(adj[v])))
                break
            if depth[v] < depth[u]:                  # back edge to an ancestor
                on_cycle[ei] = True
                cyc, w = [u], u
                while w != v:
                    if on_cycle[pedge[w]]:
                        return None                  # edge on two cycles
                    on_cycle[pedge[w]] = True
                    w = parent[w]
                    cyc.append(w)
                cycles.append(cyc)
        else:
            stack.pop()
    if -1 in depth:
        return None                                  # disconnected
    bridge_child = [v != 0 and not on_cycle[pedge[v]] for v in range(n)]
    return parent, order, cycles, bridge_child

def spanning_trees(n, edges):
    d = decompose(n, edges)
    if d is None:
        raise ValueError("not a cactus")
    total = 1
    for cyc in d[2]:
        total *= len(cyc)
    return total

Maximum-weight independent set

Maximum-weight independent set picks vertices with no edge between any two of them, maximising total weight. On a tree, the classic tree DP keeps two values per vertex: inc[v], the best weight of v's subtree with v chosen, and exc[v], the best with v not chosen. A cactus needs one addition: cycles.

Root the DFS at vertex 0. Every cycle has a unique top vertex nearest the root, and the rest of the cycle is a path hanging from it whose two end vertices are both adjacent to the top. Process vertices in reverse DFS preorder so everything below a vertex is finished first. A child joined by a bridge is folded in exactly as on a tree. For each cycle hanging from v, run a linear DP along its path, where each path vertex already carries the inc and exc values of everything hanging below it. If v is excluded, the path is unconstrained. If v is included, both path ends must be excluded, so run the path DP with the first vertex forced out and take the result with the last vertex out.

def max_weight_independent_set(n, edges, w):
    d = decompose(n, edges)
    if d is None:
        raise ValueError("not a cactus")
    parent, order, cycles, bridge_child = d
    hanging = [[] for _ in range(n)]
    for cyc in cycles:
        hanging[cyc[-1]].append(cyc[:-1])      # path below the top vertex
    inc, exc = list(w), [0] * n
    for v in reversed(order):                  # children before parents
        for path in hanging[v]:
            def walk(first_allowed):
                a = inc[path[0]] if first_allowed else float("-inf")
                b = exc[path[0]]
                for x in path[1:]:
                    a, b = b + inc[x], max(a, b) + exc[x]
                return a, b                    # last vertex in / out
            a, b = walk(True)
            exc[v] += max(a, b)                # v out: path is free
            inc[v] += walk(False)[1]           # v in: both ends out
        if bridge_child[v]:
            p = parent[v]
            inc[p] += exc[v]
            exc[p] += max(inc[v], exc[v])
    return max(inc[0], exc[0])

Every vertex and edge is touched a constant number of times, so the DP is O(n + m). Minimum-weight vertex cover follows for free: the complement of a maximum-weight independent set is a minimum-weight vertex cover, so its weight is the total weight minus the answer above.

Worked example

Take the graph in the figure: edges 0-1, 1-2, 2-0, 2-3, 3-4, 4-5, 5-6, 6-3 and 4-7, with weights 3, 1, 4, 1, 5, 9, 2, 6 on vertices 0 to 7. It has n = 8 and m = 9, well under the bound floor(3 x 7 / 2) = 10. There are c = m - n + 1 = 2 cycles, of lengths 3 and 4, so the number of spanning trees is 3 x 4 = 12; the Kirchhoff determinant gives 12 too.

For the independent set, the bridge child 7 contributes inc = 6 and exc = 0 to vertex 4. The square hangs from vertex 3 as the path 6, 5, 4. Vertex 5 is worth 9, so the best choice with 3 excluded takes 5 and 7 (vertex 4 is then out, which also lets the pendant in) for 15; with 3 included, vertices 6 and 4 must be out, which still allows 5 and 7, giving 1 + 15 = 16. The triangle hangs from vertex 0 as the path 2, 1, with vertex 3's values arriving at 2 through the bridge. The final answer is 19, reached for example by {0, 3, 5, 7} = 3 + 1 + 9 + 6. The program and an exhaustive search over all 256 subsets both return 19, and with unit weights both return 4.

Other problems and where cacti appear

The same pattern of tree DP plus a path DP per cycle solves many other problems. Distance queries between arbitrary vertices take the block-cut tree, precompute each vertex's distance to the root through the tree of blocks, and answer with a lowest common ancestor query plus a min(k, L - k) correction on the cycle where the two routes meet; the LCA article covers the query structure. Graph colouring is easy: every cactus is 3-colourable, and it is 2-colourable exactly when every cycle is even. Dominating set, maximum matching and Hamiltonicity questions all have linear-time DPs on cacti.

Cacti also appear as representations rather than inputs. Dinits, Karzanov and Lomonosov showed in 1976 that all minimum cuts of a graph can be represented by a cactus whose minimum cuts correspond to them, which is why min-cut algorithms such as Stoer-Wagner are often followed by a cactus construction when every minimum cut is needed. In comparative genomics, Paten et al. (2011) used cactus graphs to represent multiple-genome alignments, and the Progressive Cactus aligner takes its name from that structure. Network designers meet cacti as ring topologies joined at single nodes, where the property that no link is shared by two rings keeps failure analysis local to one ring.

Failure modes

• Wrong definition. Applying a vertex-cactus algorithm to an edge cactus breaks on cycles that share a vertex. State the definition in the code's docstring.
• Parallel edges. Two edges between the same pair form a cycle of length 2, and a check that skips the parent by vertex instead of by edge ID misses it. The code above skips the parent edge by ID, so a double edge is detected as a 2-cycle; decide whether your problem allows that.
• Self-loops. A loop is a cycle of length 1 that most DPs mishandle. Reject or strip loops at input.
• Disconnected input. A cactus is connected by definition. For a forest of cacti, run the algorithm per component and combine the results.
• Recursion depth. A recursive DFS on a long path of 100,000 vertices overflows Python's stack. Use an explicit stack, as above.
• Trusting the edge bound alone. m <= floor(3(n - 1) / 2) is necessary, not sufficient. Use it to reject early and still run the full DFS check.

Trade-offs

What to do next

1. Implement decompose() and confirm it rejects the 4-cycle with a chord and a disconnected graph.
2. Rebuild the worked example and check that the spanning-tree count is 12 and the independent set weight is 19.
3. Write a brute-force oracle and a random cactus generator, and compare on a few hundred small graphs before trusting your DP.
4. Extend the DP to minimum dominating set; you will need three states per vertex instead of two.
5. Build the block-cut tree from the same DFS and answer distance queries with LCA plus the cycle correction.
6. Read up on the cactus representation of minimum cuts if your application needs every minimum cut, not just one.