Chapter 3 · Directed Graphs
Cycles: Detection, Extraction, Feedback Sets
Find one cycle in linear time, find the shortest one, and know what "remove the fewest vertices to make it a DAG" costs.
- Does a cycle exist? O(n+m) — DFS back edge, or Kahn's leftovers.
- Output one cycle? O(n+m) — keep parents, walk back.
- Shortest cycle (girth)? O(nm) — BFS from every vertex; O(nω) for dense unweighted.
- Longest cycle / Hamilton? NP-complete (Held–Karp: Hamilton in O(2ⁿn²) for O(2n n2)).
- Fewest vertices hitting all cycles (feedback vertex set)? NP-hard, FPT, O(4k k n m) by bounded search tree.
#Extracting a cycle from DFS
vector<int> col(n), par(n, -1), cycle;
bool dfs(int u) {
col[u] = 1;
for (int v : g[u]) {
if (col[v] == 1) { // back edge u -> v
cycle.push_back(u);
for (int x = par[u]; x != v && x != -1; x = par[x]) cycle.push_back(x);
cycle.push_back(v);
return true;
}
if (!col[v]) { par[v] = u; if (dfs(v)) return true; }
}
col[u] = 2;
return false;
}The invariant that makes this correct: col[u] == 1 means "u is on the current recursion path", so the path par-chain from u back to v plus the edge u → v is a directed cycle (Depth-First Search, edge classification).
#Shortest cycle through BFS
For unweighted digraphs, run BFS from each s and check every edge u → v where v is an ancestor-side vertex: the answer is min(dist[u] + 1) over edges closing a loop to s; total O(nm). For undirected girth, BFS with parent-tracking from each vertex finds it in the same time (careful: parallel edges and self-loops need their own check, since the "parent exclusion" hides them).
Stop expanding when you meet an already-visited vertex that is not your parent: candidate length = d[u] + d[v] + 1. With n ≤ 2000 that is 4 × 106 per… O(nm) total, and it also gives the odd girth if you keep two copies of each vertex (parity-layered graph) — the standard trick for "shortest odd cycle".
#Feedback: what "almost a DAG" buys you
If k vertices hit every cycle, the remaining graph is a DAG. Then many NP-hard problems become O(2k · poly(n)): enumerate the state of the k special vertices, DP along the DAG order for the rest. Recognising this pattern — "the input is a DAG plus a few extra edges" — is a whole solution, not a hint.
Adding a single edge xy to a DAG creates exactly the cycles through xy: the number of new cycles is the number of paths y ⇝ x (computable by one DAG DP, DAGs and Topological Order).
Every new cycle must use the new edge; removing xy from it leaves a directed path from y to x in the original DAG, and the correspondence is bijective. ∎
That one-line argument is the core of "count cycles after adding edges" problems and of the incremental-DAG trick used in transitive-closure updates.