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
| CREATOR | Jiangdong Ai, Gregory Gutin, Hui Lei, Yongtang Shi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2608.00115