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?

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

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.