The Complexity of Mixed Arc-Disjoint Spanning Subdigraphs with Antistrong Connectivity

Abstract

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\in 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.