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$ – user97294 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)$.

| cite | improve this answer | |
  • 1
    $\begingroup$ You mean $u \in V \setminus U$? Because $U$ is a subset of $V$ so $U \setminus V$ is empty. $\endgroup$ – user97294 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