Expand description
Feedback vertex set (ALGO-CY-003).
A feedback vertex set (FVS) is a set of vertices whose removal makes the graph acyclic. Finding a minimum FVS is NP-complete on both directed and undirected graphs.
We implement a greedy heuristic: repeatedly find a cycle, remove the vertex with the highest degree from it, and repeat until no cycles remain. This is O((V+E)·|FVS|) and produces a reasonable approximation.
Counterpart of igraph_feedback_vertex_set (which uses GLPK IP in C;
here we provide a dependency-free greedy heuristic).
Enums§
- FvsAlgorithm
- Algorithm choice for computing the feedback vertex set.
Functions§
- feedback_
vertex_ set - Compute a feedback vertex set — a set of vertex IDs whose removal makes the graph acyclic.