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 edge from a vertex in $ V \setminus U$ to one in $ U$ in the graph
- There is at most one edge from a vertex in $ U$ to one in $ V \setminus U$ in the graph
(assuming there is such a subset).
The current algorithm I have works by recursively calling itself with added vertices 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?