12.17

Greedy-cycle-breaking heuristic
Idea: iteratively delete one vertex that “hits” many remaining cycles until the graph becomes acyclic.

1. While the graph contains at least one cycle
  a. Compute score(v) for every vertex that still survives.
    • simplest score = current degree(v)
    • optional: (deg(v)-1)/w(v) if vertices have weights w.
  b. Pick v\* with maximum score (break ties arbitrarily).
  c. Add v\* to the feedback-vertex set F and delete it (and its incident edges) from the graph.
2. Return F.

Why it works – Deleting a high-degree vertex eliminates many edges at once, so with high probability it intersects several cycles; once no cycle remains the remaining subgraph is a forest, so F is a (not-necessarily-minimum) feedback vertex set.

Complexity: With an adjacency list the whole loop runs in O(|E|) updates plus a O(|V| log|V|) priority queue for degree keys, i.e. O((|V|+|E|) log|V|).
Reference Python implementation (unweighted, undirected) – keeps a live degree heap and a union-find forest to decide when the graph becomes acyclic:

from collections import defaultdict import heapq def fvs_greedy(adj): # adj: dict {v:[neighbors]} deg = {v:len(adj[v]) for v in adj} live = {v:True for v in adj} heap = [(-d,v) for v,d in deg.items()] # max-heap by negating degree heapq.heapify(heap) parent,rank = {},{} def find(x): parent.setdefault(x,x) if parent[x]!=x: parent[x]=find(parent[x]) return parent[x] def union(a,b): ra,rb=find(a),find(b) if ra==rb: return False # would create cycle if rank.get(ra,0) The routine repeatedly removes the highest-degree live vertex until a forest remains, thereby outputting a quickly computed (though not optimal) feedback vertex set.

Back to Chapter 12