Complexity of some arc-partition problems for digraphs

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

33 Downloads (Pure)

Abstract

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.

OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind928
Sider (fra-til)167-182
ISSN0304-3975
DOI
StatusUdgivet - 3. sep. 2022

Bibliografisk note

Funding Information:
Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B , by research grant DIGRAPHS ANR-19-CE48-0013 and by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency ( ANR ) with the reference number ANR-17-EURE-0004 .

Publisher Copyright:
© 2022 The Author(s)

Fingeraftryk

Dyk ned i forskningsemnerne om 'Complexity of some arc-partition problems for digraphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater