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

For a given 2-partition (V₁, V₂) of the vertices of a (di)graph G, we study properties of the spanning bipartite subdigraph B_G(V₁, V₂) of G induced by those arcs/edges that have one end in each V_i, i ∈ {1, 2}. We determine, for all pairs of nonnegative integers k₁, k₂, the complexity of deciding whether G has a 2-partition V₁, V₂ such that each vertex in V_i (for i ∈ {1, 2}) has at least k_i (out-)neighbours in V_3−i. We prove that it is NP-complete to decide whether a digraph D has a 2-partition (V₁, V₂) such that each vertex in V₁ has an out-neighbour in V₂ and each vertex in V₂ has an in-neighbour in V₁ . The problem becomes polynomially solvable if we require D to be strongly connected. We give a characterisation of the structure of NP-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 NP-complete even for strong digraphs. A further result is that it is NP-complete to decide whether a given digraph D has a 2-partition (V₁, V₂) such that B_D(V₁, V₂) is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.