Pith. sign in

REVIEW 2 minor 12 references

This paper proves that two problems about packing an antistrong spanning subdigraph with a strong (or 2-edge-connected) arc-disjoint spanning subdigraph are NP-complete.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 01:12 UTC pith:FVG6KL2I

load-bearing objection First NP-completeness result looks sound; the second has a load-bearing gap in the converse: the cut equality (3) is false, so the proof that T is connected fails.

arxiv 2608.00115 v1 pith:FVG6KL2I submitted 2026-07-31 cs.DM math.CO

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

Jiangdong Ai , Gregory Gutin , Hui Lei , Yongtang Shi This is my paper
classification cs.DM math.CO MSC 05C2005C4068Q17
keywords antistrong digrapharc-disjoint spanning subdigraphsNP-completenessstrong connectivity2-edge-connectedbipartite representationHamiltonian pathoriented digraphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper settles two open decision problems in antistrong connectivity. It proves that asking whether a digraph admits two arc-disjoint spanning subdigraphs — one antistrong and the other strongly connected — is NP-complete, and that the same is true when the second requirement is that its underlying graph be 2-edge-connected. Consequently, neither problem has a polynomial-time algorithm unless P=NP. The hardness holds under strong side conditions: bounded degrees in the first case, and in the second case even for oriented digraphs that are themselves strong and antistrong, with 3-vertex-connected underlying graphs and all but two vertices of bounded degree.

Core claim

The central discovery is a pair of polynomial reductions built on the bipartite representation of digraphs, where a digraph is antistrong exactly when its bipartite representation is connected. For the antistrong-plus-strong problem, each vertex of a 2-regular digraph is replaced by a four-vertex switch whose arc set splits into a directed 4-cycle (strong) and an antistrong set; selecting the cycle parts on the arcs of a spanning strong subdigraph and the antistrong parts on the remaining arcs produces the required pair, and any required pair collapses back to such a spanning strong subdigraph. For the antistrong-plus-2-edge-connected problem, a seven-vertex oriented core containing a direct

What carries the argument

The load-bearing object is the bipartite representation B(D): split every vertex into two clones and replace every arc by an edge between the clone of its tail and the clone of its head. Antistrong connectivity of D is equivalent to connectivity of B(D), so a global trail condition becomes an ordinary connectivity condition. The two reductions then use small local gadgets whose arc sets split into two roles. The four-vertex switch Q has a directed 4-cycle C and an antistrong set F; the seven-vertex oriented core R has a directed 7-cycle C7 and an antistrong set F7 whose bipartite representation is a tree. These gadgets carry the strong/2-edge-connected side while the bipartite representation

Load-bearing premise

The conclusion inherits its hardness from two external NP-complete problems — one about spanning strong subdigraphs in 2-regular digraphs and one about Hamiltonian paths in planar cubic bipartite graphs; if either of those were actually easy, the reductions would no longer prove NP-completeness.

What would settle it

Run the two reductions on exhaustive small instances: enumerate all 2-regular digraphs on up to six vertices, build the switch-dilated digraph, and test whether the constructed digraph has the required arc-disjoint pair exactly when the source has a spanning strong subdigraph whose deletion leaves a connected underlying graph. Any mismatch — for example, a constructed digraph with the pair but a source without the subdigraph — would refute the first theorem. The analogous exhaustive check of the seven-vertex-core construction against Hamiltonian paths in small planar cubic bipartite graphs wou

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Both open questions from the antistrong-connectivity literature have negative answers unless P=NP: no polynomial-time test can decide either mixed packing problem.
  • The first NP-completeness persists for digraphs with maximum out-degree at most 4 and maximum in-degree at most 5.
  • The second NP-completeness persists even for oriented digraphs that are strong and antistrong, with 3-vertex-connected underlying graphs and all but two vertices having in/out-degree at most 4; in particular, digons are not needed for the hardness.
  • Although the packing problems are hard, the individual properties remain easy to check: antistrongness via bipartite connectivity, strongness via directed reachability, and 2-edge-connectivity via bridges. The hardness is in allocating the arc set between two incompatible requirements.
  • Any yes-instance of the second construction yields a Hamiltonian path in the source planar cubic bipartite graph, and any such path yields the required packing, so the two problems are exactly equivalent under the reduction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same 'two-role local switch' design could be tried on other mixed packings, such as pairing an antistrong subdigraph with a rooted arborescence or with a prescribed number of edge-disjoint trees; the paper does not explore these.
  • A natural strengthening, already flagged in the paper's concluding remarks, is to replace the two unbounded-degree core vertices 0 and 1 by bounded gadgets; if that works, the second result would become a fully bounded-semidegree oriented hardness statement.
  • Because the second reduction is oriented, any attempt at a polynomial algorithm for these problems cannot restrict to digraphs without digons; the hard instances already avoid opposite arcs.
  • The matroidal formulation of antistrong connectivity suggests searching for tractable special classes such as tournaments, planar digraphs, or bounded treewidth digraphs, but the paper does not address these classes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper studies two decision problems raised by Bang-Jensen et al. (2017): whether a digraph contains arc-disjoint spanning subdigraphs D1 and D2 where D1 is antistrong and D2 is strong (Problem 1), or where D2 has 2-edge-connected underlying graph (Problem 2). Theorem 3 proves Problem 1 NP-complete even with Δ+≤4 and Δ−≤5, via a reduction from the non-separating strong spanning subdigraph problem on 2-regular digraphs using a four-vertex switch. Theorem 4 proves Problem 2 NP-complete even on oriented, strong, antistrong digraphs with 3-vertex-connected underlying graph and all but two vertices of degree at most 4, via a reduction from Hamiltonian Path in planar cubic bipartite graphs using a seven-vertex core. The proofs are detailed, and the degree and connectivity promises are verified explicitly. The stress-test concern about Eq. (3) does not land: L contains x'_u for u∈U and x''_w for w∈W, so the W-spokes are incident with x'_w, which is outside L; the cut is exactly {x'_{u*}2''} as stated.

Significance. If correct, the paper gives negative answers to Questions 9.1 and 9.2 of Bang-Jensen et al. unless P=NP. It does so with unusually complete and transparent reductions: local switch/core lemmas are fully verified, the bipartite representation reduces antistrong connectivity to ordinary connectivity, and the structural promises in Theorem 4 (oriented, strong, antistrong, 3-vertex-connected underlying graph, bounded degrees except for two vertices) are proven rather than asserted. The hardness is inherited from two cited NP-complete source problems, but the reductions are self-contained beyond those citations, and the obtained restrictions are strong enough to be of independent interest.

minor comments (2)
  1. [Section 4, Eq. (3)] The apparent objection that W-spokes are in δ(L) rests on a misreading of L. The set L contains x''_w for w∈W, not x'_w; the arcs x_w0 and x_w1 are represented by edges x'_w–0'' and x'_w–1'' with both endpoints outside L. Thus Eq. (3) is correct. A short parenthetical noting this would help readers avoid the same misparse.
  2. [Lemma 9] The four displayed paths share vertices, so a reader must check that no edge is repeated before accepting the count of thirteen edges. The count is correct; the presentation could be slightly clearer if the authors explicitly say the edge sets of the paths are disjoint.

Circularity Check

0 steps flagged

No circular derivation; reductions are standard from independent NP-complete source problems, with only minor non-load-bearing self-citations.

full rationale

Both NP-completeness proofs are reductions from external, independently established NP-complete problems: Problem 7 (Bang-Jensen-Yeo [6, Theorem 1.6]) and Problem 10 (Munaro [9, Theorem 23]). These source problems do not incorporate any conclusion of this paper, and the reductions are spelled out in full: the yes directions construct D_str and D_anti explicitly, and the converses extract the source certificate (H[X], or the Hamiltonian path) from the packed subdigraphs. The antistrong characterization used throughout (Theorem 5) is cited from Bang-Jensen et al. [1], an external work, and is used as a tool, not as the result being proved. The only self-citations, [3] and [11], appear in the introductory survey of related work and are not load-bearing at any proof step; this is the single minor item reflected in the score. There is no fitted parameter renamed as a prediction and no uniqueness or ansatz imported from the authors' own prior work. Separately, the converse direction of Theorem 4 contains a nontrivial cut claim, Eq. (3), which asserts δ_{B(D(G))}(L) = {x'_u*2''} and appears to omit the W-spoke edges x'_w0'' and x'_w1''; even if that is a correctness gap, it is not circularity, because it does not make the conclusion identical to the assumptions or reduce the theorem to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The paper's central results rest on two cited NP-completeness results and the bipartite characterization of antistrong connectivity. No free parameters are fit to data. The new gadgets are fully specified and verified within the paper, so they are not unexplained invented entities.

axioms (4)
  • domain assumption Antistrong connectivity is equivalent to connectivity of the bipartite representation B(D) (Theorem 5, from Bang-Jensen et al. [1]).
    The whole paper relies on this characterization to decide antistrong connectivity through bipartite graph connectivity. It is not proven in this paper, but is a cited, established theorem.
  • domain assumption Problem 7 (non-separating strong spanning subdigraph in 2-regular digraphs) is NP-complete (Bang-Jensen–Yeo [6, Theorem 1.6]).
    Used without proof as the source for the Theorem 3 reduction.
  • domain assumption Problem 10 (Hamiltonian path in planar cubic bipartite graphs) is NP-complete (Munaro [9, Theorem 23]).
    Used without proof as the source for the Theorem 4 reduction.
  • ad hoc to paper P ≠ NP
    The conclusion 'questions have negative answers unless P=NP' invokes the P vs NP conjecture; this is standard for NP-completeness results. The NP-completeness proof itself does not depend on this.
invented entities (2)
  • Four-vertex switch Q independent evidence
    purpose: Gadget for the reduction in Theorem 3: its solid arc set C is a strong spanning subdigraph and its dashed arc set F is antistrong, allowing the packing requirement to be translated into the source problem's structure.
    The gadget's properties are fully verified in Lemma 8, and it is used as a black box in the reduction.
  • Seven-vertex oriented core R independent evidence
    purpose: Gadget for the reduction in Theorem 4: R[C7] is a directed 7-cycle and R[F7] is antistrong, with UG(R)=K7−02. It enables avoiding digons and achieving the strong/antistrong/3-vertex-connected promises.
    The core's properties are verified in Lemma 9 and (1).

pith-pipeline@v1.3.0-alltime-deepseek · 8183 in / 5788 out tokens · 42039 ms · 2026-08-04T01:12:28.009280+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2608.00115 by Gregory Gutin, Hui Lei, Jiangdong Ai, Yongtang Shi.

Figure 1
Figure 1. Figure 1: The four-vertex switch Q. Solid arcs form C, and dashed arcs form F; vertex 0 is the port. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The seven-vertex oriented core R. Solid arcs form the directed cycle C7, and dashed arcs form F7. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references

  1. [1]

    Bang-Jensen, S

    J. Bang-Jensen, S. Bessy, B. Jackson and M. Kriesell, Antistrong digraphs,J. Combin. Theory Ser. B122 (2017), 68–90

    2017

  2. [2]

    Bang-Jensen and G

    J. Bang-Jensen and G. Gutin,Digraphs: Theory, Algorithms and Applications, 2nd ed., Springer, London, 2009

    2009

  3. [3]

    Bang-Jensen, G

    J. Bang-Jensen, G. Gutin and A. Yeo, Arc-disjoint strong spanning subdigraphs of semicomplete compositions,J. Graph Theory95 (2020), 267–289

    2020

  4. [4]

    Bang-Jensen and M

    J. Bang-Jensen and M. Kriesell, Disjoint sub(di)graphs in digraphs,Electron. Notes Discrete Math.34 (2009), 179–183

    2009

  5. [5]

    Bang-Jensen and A

    J. Bang-Jensen and A. Yeo, Decomposingk-arc-strong tournaments into strong spanning subdigraphs,Combinatorica24 (2004), 331–349

    2004

  6. [6]

    Bang-Jensen and A

    J. Bang-Jensen and A. Yeo, Arc-disjoint spanning sub(di)graphs in digraphs,Theoret. Comput. Sci.438 (2012), 48–54

    2012

  7. [7]

    Edmonds, Edge-disjoint branchings, in R

    J. Edmonds, Edge-disjoint branchings, in R. Rustin (ed.),Combinatorial Algorithms, Courant Computer Science Symposium 9, Academic Press, New York, 1973, 91–96

    1973

  8. [8]

    M. R. Garey, D. S. Johnson and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete,SIAM J. Comput.5 (1976), 704–714

    1976

  9. [9]

    Munaro, On line graphs of subcubic triangle-free graphs,Discrete Math.340 (2017), 1210–1226

    A. Munaro, On line graphs of subcubic triangle-free graphs,Discrete Math.340 (2017), 1210–1226

    2017

  10. [10]

    C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs,J. London Math. Soc.36 (1961), 445–450

    1961

  11. [11]

    Y. Sun, G. Gutin and J. Ai, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs,Discrete Math.342 (2019), 2297–2305

    2019

  12. [12]

    W. T. Tutte, On the problem of decomposing a graph inton connected factors,J. London Math. Soc.36 (1961), 221–230. 11

    1961