Bipartite spanning sub(di)graphs induced by 2-partitions

For a given (Formula presented.) -partition (Formula presented.) of the vertices of a (di)graph (Formula presented.), we study properties of the spanning bipartite subdigraph (Formula presented.) of (Formula presented.) induced by those arcs/edges that have one end in each (Formula presented.). We determine, for all pairs of nonnegative integers (Formula presented.), the complexity of deciding whether (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) (for (Formula presented.)) has at least (Formula presented.) (out-)neighbours in (Formula presented.). We prove that it is (Formula presented.) -complete to decide whether a digraph (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) has an out-neighbour in (Formula presented.) and each vertex in (Formula presented.) has an in-neighbour in (Formula presented.). The problem becomes polynomially solvable if we require (Formula presented.) to be strongly connected. We give a characterisation of the structure of (Formula presented.) -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes (Formula presented.) -complete even for strong digraphs. A further result is that it is (Formula presented.) -complete to decide whether a given digraph (Formula presented.) has a (Formula presented.) -partition (Formula presented.) such that (Formula presented.) is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.