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

摘要

For a given 2-partition (V-1, V-2) of the vertices of a (di) graph G, we study properties of the spanning bipartite subdigraph B-G (V-1, V-2) of G induced by those arcs/edges that have one end in each V-i, i is an element of{1, 2}. We determine, for all pairs of nonnegative integers k(1), k(2), the complexity of deciding whether G has a 2-partition (V-1, V-2) such that each vertex in V-i (for i is an element of{1, 2}) has at least k(i) (out-) neighbours in V3-i. We prove that it is NP-complete to decide whether a digraph D has a 2-partition (V-1, V-2) such that each vertex in V-1 has an out-neighbour in V-2 and each vertex in V-2 has an in-neighbour in V-1. 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 indegree 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-1, V-2) such that B-D (V-1, V-2) is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.