Finding good 2-partitions of digraphs I. Hereditary properties

Jørgen Bang-Jensen 1 Frédéric Havet 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote following two sets of natural properties of digraphs: H ={acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E ={strongly connected, connected, minimum out- degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k1,k2, whether a given digraph has a vertex partition into two digraphs D1,D2 such that |V(Di)| ≥ ki and Di has property Pi for i = 1, 2 when P1 ∈ H and P2 ∈ H ∪ E. We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the problems when both P1 and P2 are in E is determined in the companion paper [2].when both $\mathbb{P}_1$ and $\mathbb{P}_2$ are in ${\cal E}$ is determined in the companion paper (INRIA Research report RR-8868).
Document type :
Complete list of metadatas
Contributor : Frederic Havet <>
Submitted on : Thursday, February 25, 2016 - 8:12:34 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, November 13, 2016 - 4:11:37 AM


Files produced by the author(s)


  • HAL Id : hal-01279332, version 1


Jørgen Bang-Jensen, Frédéric Havet. Finding good 2-partitions of digraphs I. Hereditary properties. [Research Report] RR-8867, INRIA Sophia Antipolis - I3S. 2016. ⟨hal-01279332⟩



Record views


Files downloads