Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem:

Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$?

(More generally, $\mathrm{MFVS}$ stands for minimal feedback vertex set, the problem of finding the smallest set of vertices such that every cycle passes through at least one of them. In general, MFVS is NP-complete.)

There is a trivial $\mathcal O(VE)$ algorithm: for every vertex $v$, use a $\mathcal O(E)$ cycle-finding algorithm, like a topological sort, to check if there is a cycle in $G$ that does not pass through $v$. I am wondering if we can do better: is it possible to solve this problem, either deterministically or probabilistically, in $\mathcal O(E^{2 - \epsilon})$, or even (ideally) in $\mathcal O(E)$?

There is a simple algorithm that seems promising: start with a set of candidate vertices $X = V$, and then alternate between:

• picking a $v \in X$ and testing if it forms a feedback vertex set by itself; if not, remove it from $X$;

• finding a random cycle in $G$, and removing all vertices from $X$ that are not on that cycle.

Unfortunately, it is possible for there to be a large set of vertices so that the vast majority of cycles contain the vast majority of those vertices, even if the answer to the decision problem is negative. So there is a class of graphs on which the above turns into a quadratic algorithm (with high probability) after all.

A vertex $v$ such that $G-v$ is acyclic is called a feedback vertex, so your problem is equivalent to deciding whether there exists at least one feedback vertex in $G$.

The paper "A linear-time algorithm for finding all feedback vertices" by Garey and Tarjan describes an algorithm that can report the set of all feedback vertices of a directed graph in linear time.

StackExchange Computer Science Q#164516, answer score: 5