Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Finding good 2-partitions of digraphs II. Enumerable properties

Jørgen Bang-Jensen 1 Nathann Cohen 2 Frédéric Havet 3 
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 : We continue the study, initiated in INRIA research report RR-8867, of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let E be the following set of properties of digraphs: E ={strongly con- nected, 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, for all choices of P1,P2 from E and all pairs of fixed positive inte- gers k1,k2, the complexity of deciding whether a digraph has a vertex partition into two digraphs D1, D2 such that Di has property Pi and |V (Di)| ≥ ki, i = 1, 2. We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the analo- gous problems when P1 ∈ H and P2 ∈ H ∪ E, where H ={acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} were completely characterized in INRIA research report RR-8867.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Thursday, February 25, 2016 - 8:26:41 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:32 AM
Long-term archiving on: : Sunday, November 13, 2016 - 4:01:07 AM


Files produced by the author(s)


  • HAL Id : hal-01279338, version 1



Jørgen Bang-Jensen, Nathann Cohen, Frédéric Havet. Finding good 2-partitions of digraphs II. Enumerable properties. [Research Report] RR-8868, INRIA Sophia Antipolis - I3S. 2016. ⟨hal-01279338⟩



Record views


Files downloads