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

Jørgen Bang-Jensen (1) , Stéphane Bessy (2) , Frédéric Havet (3) , Anders Yeo (1)

1 SDU - University of Southern Denmark
2 ALGCO - Algorithmes, Graphes et Combinatoire
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications

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.

Mots clés: Eulerian; Spanning bipartite subdigraph; Minimum out-degree; 2-partition; Strong spanning subdigraph

Domaines: Mathématique discrète [cs.DM]

Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo. Bipartite spanning sub(di)graphs induced by 2-partitions. Journal of Graph Theory, 2019, 92 (2), pp.130-151. ⟨10.1002/jgt.22444⟩. ⟨hal-02350210⟩