9
$\begingroup$

$\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:

  1. picking a $v \in X$ and testing if it forms a feedback vertex set by itself; if not, remove it from $X$;
  2. 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
+200
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When $G - v$ is acyclic, does it necessarily mean $G$ is cyclic, and does every cycle in $G$ necessarily passes through $v$? $\endgroup$
    – Kenneth Kho
    Commented Dec 21, 2023 at 0:04
  • 2
    $\begingroup$ @KennethKho, It is easy to test (in linear time) whether $G$ has any cycle. If $G$ has no cycle, then the solution to your problem is trivial. So we can WLOG assume that $G$ has a cycle. The answer to your second question is yes. Suppose there were a cycle in $G$ that didn't pass through $v$. Then that would also be a cycle in $G-v$. But if $v$ is a feedback vertex, then $G-v$ is acyclic, hence there can be no cycle in $G-v$, hence there can be no cycle that doesn't pass through $v$, i.e., every cycle in $G$ passes through $v$. $\endgroup$
    – D.W. ♦
    Commented Dec 21, 2023 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.