pith. sign in

arxiv: 2605.15773 · v1 · pith:IPGLXUO2new · submitted 2026-05-15 · 🧮 math.CO

Arc-disjoint Steiner Cycles in Digraphs

Jie Bai , Yuefang Sun , Chuchu Wang , Shanshan Yu This is my paper

Pith reviewed 2026-05-20 17:17 UTC · model grok-4.3

classification 🧮 math.CO
keywords arc-disjoint cyclesSteiner cyclesdigraphscomputational complexityEulerian digraphsplanar digraphscomplete digraphsnetwork connectivity
0
0 comments X

The pith

The maximum number of arc-disjoint S-Steiner cycles is computable in polynomial time for Eulerian, planar, and symmetric digraphs, with exact values available for complete digraph families.

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

The paper examines the maximum number of pairwise arc-disjoint directed cycles that each contain every vertex from a prescribed set S in a digraph D. It defines λ_S^c(D) as this maximum packing size and λ_k^c(D) as the minimum of λ_S^c(D) over all S of size k. The authors classify the computational complexity of computing λ_S^c(D) when D belongs to the Eulerian, planar, or symmetric class. They also derive closed-form expressions for λ_k^c(D) in complete digraphs, complete bipartite digraphs, and regular complete multipartite digraphs. These quantities measure a form of directed cycle connectivity that supports redundancy in telecommunication and transportation networks.

Core claim

We determine the complexity for λ_S^c (D) on Eulerian digraphs, planar digraphs and symmetric digraphs. We also obtain exact values of λ_k^c (D) on complete digraphs, complete bipartite digraphs and regular complete multipartite digraphs.

What carries the argument

λ_S^c(D), the maximum number of pairwise arc-disjoint directed S-Steiner cycles in the digraph D, which underpins the definition of directed cycle k-arc-connectivity λ_k^c(D).

If this is right

  • λ_S^c(D) can be computed efficiently when the input digraph is Eulerian.
  • λ_S^c(D) can be computed efficiently when the input digraph is planar.
  • λ_S^c(D) can be computed efficiently when the input digraph is symmetric.
  • λ_k^c(D) equals a simple closed-form expression for every complete digraph.
  • λ_k^c(D) equals a simple closed-form expression for every regular complete multipartite digraph.

Where Pith is reading between the lines

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

  • The tractability results may extend to other symmetric or low-treewidth digraph classes beyond those treated.
  • Exact formulas for complete digraphs could serve as benchmarks for approximation algorithms on general digraphs.
  • The connectivity measure λ_k^c(D) offers a directed analogue that could be compared directly with undirected cycle-connectivity parameters.

Load-bearing premise

The polynomial-time reductions and algorithms constructed for each digraph class correctly preserve or compute the exact Steiner-cycle packing number.

What would settle it

A concrete Eulerian digraph on which the claimed polynomial algorithm returns a value for λ_S^c(D) that differs from the true maximum packing size.

Figures

Figures reproduced from arXiv: 2605.15773 by Chuchu Wang, Jie Bai, Shanshan Yu, Yuefang Sun.

Figure 1
Figure 1. Figure 1: The Eulerian digraph G′ . Secondly, let V (D′ ) = V (G ′ ) ∪ S and A(D′ ) = A(G)∪A ′∪{−−−−→ xk−1s1, −−→t1xk, −−→xks2, −−→t2x1, −−−→ xk−2s, −−−→ txk−1}∪{−−−−→ xixi+1 | i ∈ [k]} 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The Eulerian digraph D. We will show that λ c S (D) ≥ ℓ = p + 2 if and only if there exist two arc-disjoint paths P1 and P2 in G such that Pi is an si − ti path for i ∈ [2]. This will complete the proof. If G contains a pair of arc-disjoint s1 − t1 and s2 − t2 paths, then we obtain p + 2 arc-disjoint paths: an s1 − t1 path (denoted by P1), an s2 − t2 path (denoted by P2), and p s − t paths (denoted by Pj f… view at source ↗
Figure 3
Figure 3. Figure 3: The planar digraph D. We will show that λ c S (D) ≥ ℓ = d1 + d2 if and only if there exist d1 s1 − t1 paths Pa for a ∈ [d1] and d2 s2 − t2 paths Qb for b ∈ [d2] in G that are arc-disjoint. If there exist d1 s1 − t1 paths Pa for a ∈ [d1] and d2 s2 − t2 paths Qb for b ∈ [d2] which are pairwise arc-disjoint in G, then Ca = x1eas1Pat1e ′ axkq a k,k−1xk−1 . . . x2q a 2,1x1, a ∈ [d1], C ′ b = x1p b 1,2x2 . . . x… view at source ↗
Figure 4
Figure 4. Figure 4: xixj ∈ E(G) and a replacement structure for the edge xixj to construct symmetric digraphs D are ℓ arc-disjoint S-cycles in D. Conversely, if there exist ℓ arc-disjoint S-cycles in D, then by choosing any such S-cycle, denoted by C ′ . Since S = V (G) ⊆ V (C ′ ), the directed S-cycle C ′ must pass through every vertex from V (G), with each such vertex appearing exactly once. Moreover, by the construction of… view at source ↗
read the original abstract

Let $D=(V(D), A(D))$ be a digraph of order $n$ and let $S\subseteq V(D)$ with $2\leq |S|\leq n$. A directed cycle $C$ of $D$ is called a directed $S$-Steiner cycle (or, an $S$-cycle for short) if $S\subseteq V(C)$. Steiner cycles have applications in reliable designs for telecommunication and transportation networks. Two $S$-cycles are called arc-disjoint if they have no common arcs. We use $\lambda_{S}^{c}(D)$ to denote the maximum number of pairwise arc-disjoint $S$-cycles in $D$. The directed cycle $k$-arc-connectivity of $D$ is defined as $$\lambda_{k}^{c} (D)=\min\left \{ \lambda _{S}^{c}(D)\mid S\subseteq V(D),\left | S \right | =k,2\le k\le n \right \}.$$ In this paper, we determine the complexity for $\lambda_{S}^{c} (D)$ on Eulerian digraphs, planar digraphs and symmetric digraphs. We also obtain exact values of $\lambda_{k}^{c} (D)$ on complete digraphs, complete bipartite digraphs and regular complete multipartite digraphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines λ_S^c(D) as the maximum number of pairwise arc-disjoint directed S-Steiner cycles in a digraph D for a given terminal set S, and λ_k^c(D) as the minimum of λ_S^c(D) over all S with |S|=k. It claims to classify the computational complexity of computing λ_S^c(D) on Eulerian digraphs, planar digraphs, and symmetric digraphs, and to obtain exact closed-form values of λ_k^c(D) on complete digraphs, complete bipartite digraphs, and regular complete multipartite digraphs.

Significance. If the reductions and algorithms are correct, the complexity classifications for these three digraph classes and the exact formulas for the symmetric complete families would provide a useful contribution to directed cycle packing and connectivity problems, with direct relevance to the network-design applications mentioned in the introduction.

major comments (2)
  1. [§4] §4 (Eulerian case): the claimed polynomial-time algorithm or hardness reduction must be verified to preserve the exact value of λ_S^c under the mapping; any construction that adds arcs capable of forming extra arc-disjoint S-cycles would invalidate the equivalence to the source problem.
  2. [§5] §5 (planar case): the NP-hardness reduction for planar digraphs requires an explicit argument that the maximum number of arc-disjoint S-cycles in the constructed instance equals that of the original instance; without this preservation property the hardness claim for λ_S^c on planar digraphs does not follow.
minor comments (2)
  1. [Introduction] The notation λ_k^c(D) is introduced after λ_S^c(D) but the relationship between the two parameters could be illustrated with a small example early in the paper.
  2. [Introduction] A few citations to prior work on Steiner cycles in undirected graphs are present; adding the most recent directed analogues would strengthen the literature review.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for highlighting the need for explicit preservation arguments in the reductions. We address each major comment below and will revise the paper to strengthen these aspects.

read point-by-point responses

  1. Referee: [§4] §4 (Eulerian case): the claimed polynomial-time algorithm or hardness reduction must be verified to preserve the exact value of λ_S^c under the mapping; any construction that adds arcs capable of forming extra arc-disjoint S-cycles would invalidate the equivalence to the source problem.

    Authors: We agree that an explicit verification of value preservation is essential. In Section 4 the reduction augments the input digraph to an Eulerian digraph by adding a small number of arcs whose endpoints lie outside S or are constrained so that they cannot participate in any new S-Steiner cycle without sharing arcs with cycles already counted in the original instance. Nevertheless, to make the argument fully rigorous we will insert a new lemma (Lemma 4.X) that proves λ_S^c(D') = λ_S^c(D) for the constructed instance D'. The revised manuscript will contain this lemma together with a short proof that no additional arc-disjoint S-cycle can arise from the augmentation. revision: yes

  2. Referee: [§5] §5 (planar case): the NP-hardness reduction for planar digraphs requires an explicit argument that the maximum number of arc-disjoint S-cycles in the constructed instance equals that of the original instance; without this preservation property the hardness claim for λ_S^c on planar digraphs does not follow.

    Authors: We concur that the planar reduction in Section 5 must be accompanied by a clear equality statement. The gadget construction replaces each original arc by a planar path of length two whose internal vertex has degree two; any S-cycle in the new planar digraph must traverse these paths in their entirety and therefore corresponds one-to-one with an S-cycle in the source instance. We will add an explicit lemma (Lemma 5.Y) establishing that λ_S^c(D') = λ_S^c(D) and that the constructed digraph remains planar. This lemma will be placed immediately after the description of the reduction. revision: yes

Circularity Check

0 steps flagged

No circularity; definitions and results are independent

full rationale

The paper explicitly defines λ_S^c(D) as the maximum number of arc-disjoint S-cycles and λ_k^c(D) as the minimum of those over |S|=k. It then states complexity classifications for specific digraph classes and exact values for complete and multipartite digraphs. These are presented as outcomes of polynomial reductions or algorithms constructed for each class, with no equations or steps that redefine a quantity in terms of itself or rename a fitted input as a prediction. No self-citation is invoked as load-bearing for the central claims, and the results do not reduce to the input definitions by construction. The derivation chain consists of standard graph-theoretic arguments that remain independent of the quantities being computed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard axioms of directed graphs, directed cycles, and arc-disjointness; no free parameters, invented entities, or ad-hoc assumptions beyond ordinary graph-theoretic definitions are visible in the abstract.

axioms (1)
  • standard math Standard definitions of digraph, directed cycle, and arc-disjointness hold.
    The entire development is built on these background notions of graph theory.

pith-pipeline@v0.9.0 · 5773 in / 1276 out tokens · 59178 ms · 2026-05-20T17:17:01.186306+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Bang-Jensen and G

    J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Ap- plications, 2nd Edition, Springer, London, 2009

    work page 2009

  2. [2]

    Bondy and U.S.R

    J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, Berlin, 2008

    work page 2008

  3. [3]

    Cheriyan and M

    J. Cheriyan and M. Salavatipour, Hardness and approximation results for packing Steiner trees, Algorithmica, 45, 2006, 21–43

    work page 2006

  4. [4]

    Forture, J

    S. Forture, J. Hopcroft and J. Wyllie, The directed subgraph homeo- morphism problem, Theoret. Comput. Sci., 10, 1980, 111–121. 15

    work page 1980

  5. [5]

    Gr¨ otschel, A

    M. Gr¨ otschel, A. Martin and R. Weismantel, The Steiner tree packing problem in VLSI design, Math. Program., 78, 1997, 265–281

    work page 1997

  6. [6]

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

    work page 1976

  7. [7]

    R. M. Karp, Reducibility among combinatorial problems, in Complex- ity of Computer Computer Communications, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, 85–103

    work page 1972

  8. [8]

    Li and Y

    X. Li and Y. Mao, Generalized Connectivity of Graphs, Springer, Switzerland, 2016

    work page 2016

  9. [9]

    Ng, Hamiltonian decoposition of complete regular multipartite di- graphs, Discrete Math., 177(1-3), 1997, 279–285

    L.L. Ng, Hamiltonian decoposition of complete regular multipartite di- graphs, Discrete Math., 177(1-3), 1997, 279–285

    work page 1997

  10. [10]

    Naves, The hardness of routing two pairs on one face, Math

    G. Naves, The hardness of routing two pairs on one face, Math. Pro- gram., 131(1), 2012, 49–69

    work page 2012

  11. [11]

    Picouleau, Complexity of the Hamiltonian cycle in regular graph problem., Theor

    C. Picouleau, Complexity of the Hamiltonian cycle in regular graph problem., Theor. Comput. Sci., 131(2), 1994, 463–73

    work page 1994

  12. [12]

    Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition, Kluwer Acad

    N. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition, Kluwer Acad. Pub., London, 1999

    work page 1999

  13. [13]

    Sun, Steiner Type Packing Problems in Digraphs, SpringerBriefs in Mathematics, Springer, Singapore, 2026

    Y. Sun, Steiner Type Packing Problems in Digraphs, SpringerBriefs in Mathematics, Springer, Singapore, 2026

    work page 2026

  14. [14]

    Sun and G

    Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs, Graphs Combin., 37, 2021, 951–970

    work page 2021

  15. [15]

    Y. Sun, G. Gutin, A. Yeo and X. Zhang, Strong subgraphk- connectivity, J. Graph Theory, 92(1), 2019, 5–18

    work page 2019

  16. [16]

    Y. Sun, G. Gutin and X. Zhang, Packing strong subgraph in digraphs, Discrete Optim., 46, 2022, Article 100745

    work page 2022

  17. [17]

    Sun and Z

    Y. Sun and Z. Jin, Perfect out-forest problem and directed Steiner cycle packing problem, Discrete Appl. Math., 366, 2025, 201–209

    work page 2025

  18. [18]

    Sun and A

    Y. Sun and A. Yeo, Directed Steiner tree packing and directed tree connectivity, J. Graph Theory, 102(1), 2023, 86–106

    work page 2023

  19. [19]

    Steiglitz, P

    K. Steiglitz, P. Weiner and D. Kleitman, The design of minimum-cost survivable networks, IEEE Trans. Circuit Theory, 16(4), 1969, 455–460. 16

    work page 1969

  20. [20]

    T. W. Tillson, A Hamiltonian decomposition ofK ∗ 2m, 2m≥8, J. Com- bin. Theory Ser. B, 29(1), 1980, 68–74

    work page 1980

  21. [21]

    Wang and Y

    C. Wang and Y. Sun, Directed cyclek-connectivity of complete digraphs and complete regular bipartite digraphs, Discrete Appl. Math., 358, 2024, 203–213. 17

    work page 2024