Complexity of some arc-partition problems for digraphs Article - Septembre 2022

Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta

Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta, « Complexity of some arc-partition problems for digraphs  », Theoretical Computer Science, septembre 2022, pp. 167-182. ISSN 1879-2294

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.

Voir la notice complète sur HAL

Actualités