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
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01279338
Contributor : Frederic Havet <>
Submitted on : Thursday, February 25, 2016 - 8:26:41 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, November 13, 2016 - 4:01:07 AM

File

RR-8868.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01279338, version 1

Relations

Citation

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⟩

Share

Metrics

Record views

407

Files downloads

173