Bipartite spanning sub(di)graphs induced by 2-partitions: BANG-JENSEN et al.

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