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
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02350210
Contributor : Frederic Havet <>
Submitted on : Wednesday, November 6, 2019 - 12:51:42 AM
Last modification on : Wednesday, November 13, 2019 - 7:54:30 PM

File

Bipartite-revise.pdf
Files produced by the author(s)

Identifiers

Citation

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, Wiley, 2019, 92 (2), pp.130-151. ⟨10.1002/jgt.22444⟩. ⟨hal-02350210⟩

Share

Metrics

Record views

29

Files downloads

198