Skip to main content
Computer Science

Return to Question

Notice removed Draw attention by Mees de Vries
Bounty Ended with Steven's answer chosen by Mees de Vries
Notice added Draw attention by Mees de Vries
Bounty Started worth 200 reputation by Mees de Vries
added 72 characters in body
Source Link
Mees de Vries
Mees de Vries
  • 353
  • 2
  • 16

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

$\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, use a $\mathcal O(E)$ cycle-finding algorithm, like a topological sort. 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.

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

Source Link
Mees de Vries
Mees de Vries
  • 353
  • 2
  • 16

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, use a $\mathcal O(E)$ cycle-finding algorithm, like a topological sort. 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.