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

Jiangdong Ai, Gregory Gutin, Hui Lei, Yongtang Shi · 2026

Read The Complexity of Mixed Arc-Disjoint Spanning Subdigraphs with Antistrong Connectivity by Jiangdong Ai, Gregory Gutin, Hui Lei, Yongtang Shi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00115.txt.

Description

Ai, Gutin, Lei, and Shi settle the complexity of two spanning subdigraph problems. A trail is antidirected when its arcs alternate in direction. A digraph is antistrong when such trails join every ordered vertex pair. Bang-Jensen and co-authors posed the two problems in 2017. Each asks for paired spanning subdigraphs with set connectivity traits.

Both decision problems prove NP-complete, they show. The first stays hard even with small in- and out-degree caps. The second stays hard for strong, antistrong oriented digraphs with tight degree bounds. Its underlying graphs can be 3-vertex-connected in the hard cases. The result does not rely on digons, they note. Polynomial-time hopes for both problems are thus closed.

Catalog record

CREATORJiangdong Ai, Gregory Gutin, Hui Lei, Yongtang Shi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2608.00115

Browse the full library · About the Tower of Babel