{"id":"arxiv/2608.00115","url":"https://arxiv.org/abs/2608.00115","tags":["cs.DM","math.CO"],"score":0,"title":"The Complexity of Mixed Arc-Disjoint Spanning Subdigraphs with Antistrong Connectivity","domain":"cs.DM","source":"arxiv","authors":["Jiangdong Ai","Gregory Gutin","Hui Lei","Yongtang Shi"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}