Open arc-decomposition problems of Bang-Jensen, Bessy, Gonçalves, and Picasarri-Arrieta

The entry concerns four specific arc-decomposition decision problems posed in earlier work by Bang-Jensen, Bessy, Gonçalves, and Picasarri-Arrieta. It does not claim to resolve every open question about decomposing directed graphs.

Known results

• Bang-Jensen, Bessy, Gonçalves, and Picasarri-Arrieta (2022) reported a complete polynomial-time versus NP-complete classification of $120$ arc-partitioning problems for digraphs.
• Their results include polynomial-time cases such as $(\text{connected},\text{connected})$ and $($out-branching$,$out-branching$)$.
• They reported NP-completeness for $($out-branching$,$in-branching$)$, $($strongly connected$,$strongly connected$)$, and related pairs.
• A 2021 survey of the area listed broader existence conjectures involving $k$-arc-strong digraphs, some of which remain distinct from the four problems here.

August 2026 claimed classification

A newly reported paper claims exact complexity classifications for the four specified open combinations, thereby settling them conditionally where NP-completeness is proved: the corresponding positive decomposition questions have negative answers unless $P=NP$. A related arXiv paper explicitly claims NP-completeness for two antistrong decomposition problems, with strong degree and connectivity restrictions.

Current status (as of August 2026): Four specified problems are claimed settled by complexity classifications, but the claim is unverified; broader arc-decomposition questions remain open.