2026/07/31 by Jiangdong Ai, Gregory Gutin, Hui Lei +1
Computer Science · Mathematics · #cs.DM #math.CO
11 pages
arxiv created 2026/07/31 · arxiv updated 2026/08/04
A trail is antidirected if its arcs alternate between forward and backward. A digraph D is antistrong if, for every ordered pair of distinct vertices x,y∈ V(D), it contains a forward antidirected (x,y)-trail. Bang-Jensen, Bessy, Jackson and Kriesell [J. Combin. Theory Ser. B 122 (2017), 68--90] introduced antistrong connectivity and posed two problems concerning mixed arc-disjoint spanning subdigraphs. In the first problem, one seeks an antistrong spanning subdigraph and an arc-disjoint strong spanning subdigraph. In the second, strong connectivity is replaced by the requirement that the underlying graph of the second subdigraph be 2-edge-connected. Bang-Jensen et al. asked whether each of the two problems can be solved in polynomial time. We prove that the two associated decision problems are NP-complete. The first remains NP-complete for digraphs with maximum out-degree at most four and maximum in-degree at most five. The second remains NP-complete even for oriented digraphs that are strong and antistrong, whose underlying graphs are 3-vertex-connected, and in which all but at most two vertices have both in-degree and out-degree at most four. In particular, the latter hardness result does not rely on digons.