## Abstract

We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A_{1},A_{2}) of its arc set such that each of the corresponding digraphs D_{1}=(V,A_{1}) and D_{2}=(V,A_{2}) 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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Theoretical Computer Science |

Vol/bind | 928 |

Sider (fra-til) | 167-182 |

ISSN | 0304-3975 |

DOI | |

Status | Udgivet - 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)