# Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set

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?

• 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. Dec 31, 2018 at 12:17
• Thanks, that's useful, I didn't think about that!
– user97294
Dec 31, 2018 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)$$.
• You mean $u \in V \setminus U$? Because $U$ is a subset of $V$ so $U \setminus V$ is empty.
• Sorry, I meant $u \in U$, you're of course right that $U \setminus V$ is empty! Dec 31, 2018 at 14:54