# Karp hardness of two vertex sets in a digraph

Given a digraph $$G(V,A)$$ and a number $$k$$, we want to find two vertex subsets $$S,T\subseteq V$$ such that:

1. $$|S|+|T|=k$$
2. For every $$v\notin S\cup T$$, $$v$$ has no arcs coming to $$S$$, and no arcs coming from $$T$$. In other words, from $$v$$'s point of view, $$S$$ is the source, $$T$$ is the terminal. Hence their names.

So, can this be solved by an efficient algorithm or it is NP-complete?

• Can $A\cap B\neq \emptyset$? – xskxzr Jan 12 at 13:14
• Yes, $S\cap T\neq\emptyset$ can appear in a feasible solution. – Thinh D. Nguyen Jan 12 at 13:54