I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:

  1. $U$ contains at least two vertices, and $U \neq V$
  2. There is at most one vertex in $V \setminus U$ connected to a vertex in $U$
  3. There is at most one vertex in $U$ connected to a vertex in $V \setminus U$

(assuming there is such a subset).

The current algorithm I have works by recursively calling itself with one added vertex until the set has the appropriate conditions, but it's much too slow.

Is there any algorithm I could use to do this more efficiently?

  • 1
    $\begingroup$ By "guessing" U, you get a running time of 2^n. Have you tried to see what happens if you "know" the "entry-point" and "exit-point" of U? If you can solve it then in p(n, m) time, then the algorithm takes n² p(n, m) in total. $\endgroup$ – Pål GD Dec 31 '18 at 12:17
  • $\begingroup$ Thanks, that's useful, I didn't think about that! $\endgroup$ – Stefan Dec 31 '18 at 12:58

Let's name the vertices $v \in V \setminus U$ and $u \in U$ the vertices that are allowed to have out-neighbors anywhere.

Suppose that we know the vertex $u$ and delete all its out-edges.

Now we are looking for a vertex $v$ that "separates" the graph in two components, $V \ni v$ and $U \ni u$.

We can find $u$ in $O(n)$ time by trying all possibilities. We can also find the strongly connected components in $O(n + m)$ time. In this graph, we must find $v$ with the above property. That can be done in linear time $O(n + m)$. Hence it all runs in $O(n(n+m))$ time, which is at most $O(n^3)$.

  • 1
    $\begingroup$ You mean $u \in V \setminus U$? Because $U$ is a subset of $V$ so $U \setminus V$ is empty. $\endgroup$ – Stefan Dec 31 '18 at 14:52
  • 1
    $\begingroup$ Sorry, I meant $u \in U$, you're of course right that $U \setminus V$ is empty! $\endgroup$ – Pål GD Dec 31 '18 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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