Complexity of some arc-partition problems for digraphs

J. Bang-Jensen*, S. Bessy, D. Gonçalves, L. Picasarri-Arrieta

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

14 Downloads (Pure)


We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.

Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)167-182
Publication statusPublished - 3. Sept 2022


  • Acyclic digraph
  • Arc-partitions
  • Branchings
  • Cycle factor
  • Digraphs
  • NP-complete
  • Polynomial algorithm
  • Strong subdigraphs


Dive into the research topics of 'Complexity of some arc-partition problems for digraphs'. Together they form a unique fingerprint.

Cite this