I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:
- $U$ contains at least two vertices, and $U \neq V$
- There is at most one vertex in $V \setminus U$ connected to a vertex in $U$
- 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?