Minimum Cycle Basis Enumeration — Problem Statement & Solution Guide

GraphsHardCycle Detection in Graph

TimeO(m·n log n + m·n·α(m)) // shortest‑path + greedy selection with union‑find on bitsets

SpaceO(m·n) // storage for candidate cycles and bitset matrix

Problem Description

Given an undirected graph represented as an adjacency list, find a minimum cycle basis, which is a set of simple cycles with the minimum total length such that any other cycle in the graph can be expressed as a linear combination of these cycles. The graph may have no cycles, multiple cycles with the same length, or cycles with negative lengths.

DSA Pattern Breakdown

"Minimum Cycle Basis Enumeration"

hard

WHY DOES IT MATTER?

Minimum cycle bases capture the essential redundancy of a network, enabling compact representation of all cycles for tasks like electrical circuit analysis, network reliability, and graph compression. Mastering this pattern demonstrates a candidate’s ability to work with linear algebra on graphs, matroid theory, and advanced greedy strategies—skills that differentiate senior engineers.

OPTIMIZATION CHALLENGE

The breakthrough is restricting the exponential family of cycles to a polynomial‑size candidate set (Horton’s O(m·n) cycles) using fundamental cycles from shortest‑path trees, then applying a matroid‑greedy selection with binary independence checks. This reduces both time and space from exponential to polynomial.

REAL-WORLD CONNECTION

Think of a power grid where each loop can carry circulating currents; the MCB is the smallest set of loops you need to monitor to infer any possible circulating current pattern. In distributed systems, it mirrors the minimal set of dependency cycles you must break to achieve eventual consistency.

When coding, pre‑compute all‑pairs shortest paths once (or use Johnson’s algorithm for sparse graphs) and store parent pointers to reconstruct fundamental cycles on the fly. Use a bitset representation for incidence vectors to speed up independence checks with XOR and rank updates.

COMPLEXITY AT A GLANCE

⏱ Time:O(m·n log n + m·n·α(m)) // shortest‑path + greedy selection with union‑find on bitsets

💾 Space:O(m·n) // storage for candidate cycles and bitset matrix

Core Theory — Why This Approach?

A minimum cycle basis (MCB) of an undirected graph is a smallest‑weight set of simple cycles such that every other cycle can be expressed as a binary XOR (symmetric difference) of cycles in the set. The weight of a basis is the sum of the lengths (or costs) of its constituent cycles, and the goal is to minimise this sum. The classic approach relies on linear algebra over GF(2): each cycle corresponds to a binary incidence vector over the edge set, and the collection of all cycles forms a vector space. The MCB problem is equivalent to finding a basis of this space with minimum total weight, which can be solved by a greedy algorithm that sorts candidate cycles by weight and adds them if they increase the rank of the current set. This is analogous to Kruskal’s algorithm for minimum spanning trees, but operates in the cycle space rather than the vertex space.

Naïve enumeration—generating all simple cycles, sorting them, and performing Gaussian elimination—fails because the number of simple cycles can be exponential in the number of vertices (e.g., in dense graphs or grids). Storing all cycles quickly exhausts memory, and the elimination step becomes O(m^3) where m is the number of edges. The optimal paradigm leverages the fact that a fundamental cycle basis can be built from a spanning tree: each non‑tree edge creates a unique fundamental cycle. By iteratively improving this basis using shortest‑path queries (often via Dijkstra or Bellman‑Ford for negative weights) and applying the Horton algorithm, we can generate a candidate set of O(m·n) cycles, then run a greedy selection with union‑find on the binary matroid, achieving polynomial time. Advanced implementations use fast matrix multiplication or randomized contraction to reach O(m^2 n / log n) or better, but the core idea remains: restrict candidate cycles to a manageable polynomial family and apply a matroid‑greedy selection.

Interview Questions on This Problem

Q1How would you compute a minimum cycle basis in an undirected graph with possible negative edge weights?

First, run a shortest‑path algorithm that handles negative weights (Bellman‑Ford) from each vertex to compute all‑pairs shortest paths. For each non‑tree edge, form its fundamental cycle using the shortest path between its endpoints in the current spanning tree. Collect all such cycles (Horton’s set), sort them by total weight, and greedily add a cycle to the basis if its incidence vector is linearly independent of previously chosen cycles (checked via union‑find on a binary matrix). This yields a minimum‑weight basis even with negative edges because the greedy matroid property holds over GF(2).

Q2Why does a simple greedy algorithm that picks the shortest cycle repeatedly fail to produce a minimum cycle basis?

Greedy selection without respecting linear independence can pick cycles that are linear combinations of earlier cycles, leaving the basis rank deficient or forcing later inclusion of longer cycles to achieve full rank. The matroid property guarantees optimality only when each addition strictly increases the rank of the cycle space; ignoring this can lead to sub‑optimal total weight.

Q3Explain how the concept of a binary matroid is used in the minimum cycle basis problem and how it relates to Kruskal’s algorithm.

The set of edge‑incidence vectors of cycles forms a binary matroid where independence corresponds to linear independence over GF(2). Kruskal’s algorithm is a greedy algorithm on a graphic matroid (edges forming a forest). Similarly, the greedy algorithm for MCB works on the cycle matroid: we sort candidate cycles by weight and add a cycle only if it increases the rank (i.e., its vector is not a XOR of previously selected vectors). This matroid‑greedy framework guarantees the resulting basis is minimum‑weight.

Examples

Example 1

Input

{"graph":{"0":["1","2"],"1":["0","2"],"2":["0","1"]}}

Output

[["0","1","2","0"]]

Explanation: Step-by-step: with input graph {"0": ["1", "2"], "1": ["0", "2"], "2": ["0", "1"]}, we find a minimum cycle basis by identifying all simple cycles in the graph. In this case, there is only one cycle: ["0", "1", "2", "0"].

Example 2

Input

{"graph":{"0":["1","2"],"1":["0","2","3"],"2":["0","1"],"3":["1"]}}

Output

[["0","1","2","0"],["0","1","3","0"]]

Explanation: Step-by-step: with input graph {"0": ["1", "2"], "1": ["0", "2", "3"], "2": ["0", "1"], "3": ["1"]}, we find a minimum cycle basis by identifying all simple cycles in the graph. In this case, there are two cycles: ["0", "1", "2", "0"] and ["0", "1", "3", "0"].

Constraints

The graph is represented as an adjacency list.
The graph may contain self-loops and parallel edges.
The graph has at most 100 vertices and 500 edges.
All edge weights are assumed to be 1 for simplicity.

Optimal Approach & Strategy

Generate O(m·n) fundamental cycles via shortest‑path trees (Horton), sort them, and greedily select cycles that increase the binary rank of the basis using fast bitset XOR checks, achieving polynomial time.

Brute Force Approach

Enumerate every simple cycle, sort them by length, and repeatedly add the shortest cycle that is not a XOR of previously chosen cycles; this is exponential because the number of simple cycles can be O(2^n).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(m·n log n + m·n·α(m)) // shortest‑path + greedy selection with union‑find on bitsets

function solution(graph) {
    const visited = new Set();
    const cycles = [];
    for (const node in graph) {
        if (!visited.has(node)) {
            dfs(graph, node, visited, cycles, []);
        }
    }
    return cycles;
}

function dfs(graph, node, visited, cycles, path) {
    visited.add(node);
    path.push(node);
    for (const neighbor of graph[node]) {
        if (neighbor === path[0] && path.length > 1) {
            cycles.push([...path]);
        } else if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited, cycles, path);
        }
    }
    path.pop();
    visited.delete(node);
}

class Solution {
public:
    vector<vector<string>> solution(unordered_map<string, vector<string>> graph) {
        unordered_set<string> visited;
        vector<vector<string>> cycles;
        for (auto& node : graph) {
            if (visited.find(node.first) == visited.end()) {
                dfs(graph, node.first, visited, cycles, {});
            }
        }
        return cycles;
    }

    void dfs(unordered_map<string, vector<string>> graph, string node, unordered_set<string>& visited, vector<vector<string>>& cycles, vector<string> path) {
        visited.insert(node);
        path.push_back(node);
        for (const string& neighbor : graph[node]) {
            if (neighbor == path[0] && path.size() > 1) {
                cycles.push_back(path);
            } else if (visited.find(neighbor) == visited.end()) {
                dfs(graph, neighbor, visited, cycles, path);
            }
        }
        path.pop_back();
        visited.erase(node);
    }
};

import java.util.*;
public class Solution {
    public List<List<String>> solution(Map<String, List<String>> graph) {
        Set<String> visited = new HashSet<>();
        List<List<String>> cycles = new ArrayList<>();
        for (String node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs(graph, node, visited, cycles, new ArrayList<>());
            }
        }
        return cycles;
    }

    private void dfs(Map<String, List<String>> graph, String node, Set<String> visited, List<List<String>> cycles, List<String> path) {
        visited.add(node);
        path.add(node);
        for (String neighbor : graph.get(node)) {
            if (neighbor.equals(path.get(0)) && path.size() > 1) {
                cycles.add(new ArrayList<>(path));
            } else if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, cycles, path);
            }
        }
        path.remove(path.size() - 1);
        visited.remove(node);
    }
}

def solution(graph):
    visited = set()
    cycles = []
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited, cycles, [])
    return cycles

def dfs(graph, node, visited, cycles, path):
    visited.add(node)
    path.append(node)
    for neighbor in graph[node]:
        if neighbor == path[0] and len(path) > 1:
            cycles.append(path[:])
        elif neighbor not in visited:
            dfs(graph, neighbor, visited, cycles, path)
    path.pop()
    visited.remove(node)

function solution(graph) {
    const visited = new Set();
    const cycles = [];
    for (const node in graph) {
        if (!visited.has(node)) {
            dfs(graph, node, visited, cycles, []);
        }
    }
    return cycles;
}

function dfs(graph, node, visited, cycles, path) {
    visited.add(node);
    path.push(node);
    for (const neighbor of graph[node]) {
        if (neighbor === path[0] && path.length > 1) {
            cycles.push([...path]);
        } else if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited, cycles, path);
        }
    }
    path.pop();
    visited.delete(node);
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Minimum Cycle Basis Enumeration Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Minimum Cycle Basis Enumeration — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor