pith. sign in

arxiv: 2206.12092 · v6 · pith:DD447ULLnew · submitted 2022-06-24 · 🧮 math.CO

Steiner Type Packing Problems in Digraphs: A Survey

Yuefang Sun This is my paper

Pith reviewed 2026-05-24 11:52 UTC · model grok-4.3

classification 🧮 math.CO
keywords directed graphsSteiner tree packinggraph packingdigraphsSteiner problemssurveycombinatorial optimizationopen problems
0
0 comments X

The pith

This survey overviews known results on directed Steiner type packing problems in digraphs and lists open conjectures.

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

The paper establishes a structured overview of directed Steiner packing problems as a natural extension of the undirected Steiner tree packing problem. It organizes results into sections on tree packing, path packing, pendant tree packing, strong subgraph packing, arc decomposition, and cycle packing. A sympathetic reader would value this as a consolidated reference point that identifies what results are established and which directions remain open for further work in combinatorial optimization on digraphs.

Core claim

The survey claims that several directed Steiner type packing problems in digraphs have been studied in the literature, and it collects the known results across these variants while presenting conjectures and open problems to guide additional research.

What carries the argument

The classification of problems into the seven sections covering directed Steiner tree packing, directed Steiner path packing, directed pendant Steiner tree packing, strong subgraph packing, strong arc decomposition, and directed Steiner cycle packing, which serves to organize the literature.

Load-bearing premise

The survey assumes that its chosen division into problem types and the cited papers together give a representative overview of the field without major omissions.

What would settle it

Discovery of a substantial body of results on any of the listed directed Steiner packing problems that the survey neither mentions nor references.

Figures

Figures reproduced from arXiv: 2206.12092 by Yuefang Sun.

Figure 1
Figure 1. Figure 1: Digraph S4 The following result extends Theorem 5.1 to locally semicomplete di￾graphs. Theorem 5.2 [7] A 2-arc-strong locally semicomplete digraph D has a strong arc decomposition if and only if D is not the second power of an even cycle. 5.2 Digraph compositions After that, Sun, Gutin and Ai [58] continued research on strong arc decompositions in classes of digraphs and consider digraph compositions and p… view at source ↗
read the original abstract

Graph packing problem is one of the central problems in graph theory and combinatorial optimization. The famous Steiner tree packing problem in undirected graphs has become an well-established area. It is natural to extend this problem to digraphs, and such problems in digraphs are called directed Steiner type packing problems. In this survey we overview known results on several directed Steiner type packing problems. The paper is divided into seven sections: introduction, directed Steiner tree packing problem, directed Steiner path packing problem, directed pendant Steiner tree packing problem, strong subgraph packing problem, strong arc decomposition problem, directed Steiner cycle packing problem. This survey also contains some conjectures and open problems for further study.

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

0 major / 2 minor

Summary. The manuscript is a survey paper that overviews known results on directed Steiner type packing problems in digraphs. It is organized into seven sections: an introduction followed by dedicated sections on the directed Steiner tree packing problem, directed Steiner path packing problem, directed pendant Steiner tree packing problem, strong subgraph packing problem, strong arc decomposition problem, and directed Steiner cycle packing problem. The survey also presents some conjectures and open problems for further study.

Significance. If the cited results are accurately represented and the coverage is representative, the survey would provide a consolidated reference for researchers in graph theory and combinatorial optimization working on extensions of Steiner packing problems to directed graphs, while the included conjectures could help guide future work.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'an well-established area' contains a grammatical error and should read 'a well-established area'.
  2. [Abstract] Abstract: the sentence 'In this survey we overview known results...' would read more naturally as 'This survey overviews known results...' or 'In this survey, we overview known results...'.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our survey and the recommendation for minor revision. No major comments were provided in the report, so we have no specific points to address at this time. We remain available to incorporate any minor suggestions or clarifications in a revised version.

Circularity Check

0 steps flagged

No significant circularity in survey structure

full rationale

This is a survey paper that overviews known results on directed Steiner-type packing problems from external literature, lists sections on specific problem variants, and includes conjectures/open problems. No derivations, equations, fitted parameters, or new claims are constructed from the paper's own inputs; validity rests on accurate citation of prior work rather than internal reduction. The modest goal of providing an overview is self-contained against external benchmarks with no load-bearing self-citation chains or self-definitional steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper with no new mathematical content, free parameters, axioms, or invented entities introduced.

pith-pipeline@v0.9.0 · 5627 in / 913 out tokens · 23816 ms · 2026-05-24T11:52:17.060757+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

68 extracted references · 68 canonical work pages

  1. [1]

    Bang-Jensen, Edge-disjoint in- and out-branchings i n tournaments and related path problems, J

    J. Bang-Jensen, Edge-disjoint in- and out-branchings i n tournaments and related path problems, J. Combin. Theory Ser. B, 51(1), 1 991, 1–23

    work page

  2. [2]

    Bang-Jensen, A

    J. Bang-Jensen, A. Frank and B. Jackson, Preserving and i ncreasing local edge-connectivity in mixed graphs, SIAM J. Discrete M ath., 8, 1995, 155–178

    work page 1995

  3. [3]

    Bang-Jensen and G

    J. Bang-Jensen and G. Gutin, Generalizations of tournam ents: a survey, J. Graph Theory, 28, 1998, 171–202

    work page 1998

  4. [4]

    Bang-Jensen and G

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

    work page 2009

  5. [5]

    Bang-Jensen, G

    J. Bang-Jensen, G. Gutin and A. Yeo, Arc-disjoint strong spanning subgraphs of semicomplete compositions, J. Graph Theory, 9 5(2), 2020, 267–289

    work page 2020

  6. [6]

    Bang-Jensen and J

    J. Bang-Jensen and J. Huang, Quasi-transitive digraphs , J. Graph The- ory, 20(2), 1995, 141–161

    work page 1995

  7. [7]

    Bang-Jensen and J

    J. Bang-Jensen and J. Huang, Decomposing locally semico mplete di- graphs into strong spanning subdigraphs, J. Combin. Theory Ser. B, 102, 2012, 701–714

    work page 2012

  8. [8]

    Bang-Jensen and J

    J. Bang-Jensen and J. Huang, Arc-disjoint in- and out-br anchings rooted at the same vertex in locally semicomplete digraphs, J. Graph Theory, 77, 2014, 278–298

    work page 2014

  9. [9]

    Bang-Jensen and A

    J. Bang-Jensen and A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica, 24(3), 2 004, 331– 349

    work page

  10. [10]

    Berczi, E

    K. Berczi, E. R. Kovacs, A note on strongly edge-disjoin t arborescences, EGRES TR-2011-04

    work page 2011

  11. [11]

    L. Chen, X. Li, M. Liu and Y. Mao, A solution to a conjectur e on the generalized connectivity of graphs, J. Combin. Optim., 33(1), 2017, 275–282

    work page 2017

  12. [12]

    Cheriyan and M

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

    work page 2006

  13. [13]

    Chudnovsky, A

    M. Chudnovsky, A. Scott and P.D. Seymour, Disjoint path s in unions of tournaments, J. Combin. Theory Ser. B, 135, 2019, 238–255

    work page 2019

  14. [14]

    DeVos, J

    M. DeVos, J. McDonald and I. Pivotto, Packing Steiner tr ees, J. Com- bin. Theory Ser. B, 119, 2016, 178–213

    work page 2016

  15. [15]

    Y. Dong, G. Gutin and Y. Sun, Strong subgraph 2-arc-conn ectivity and arc-strong connectivity of Cartesian product of digrap hs, Discuss. Math. Graph Theory, doi:10.7151/dmgt.2479. 30

    work page doi:10.7151/dmgt.2479

  16. [16]

    Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms (B

    J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms (B. Rustin ed.), Academic Press, 1973, 91–96

    work page 1973

  17. [17]

    Feige, M

    U. Feige, M. Halldorsson, G. Kortsarz and A. Srinivasan , Approximat- ing the domatic number, SIAM J. Comput., 32(1), 2002, 172–19 5

    work page 2002

  18. [18]

    Fortune, J

    S. Fortune, J. Hopcroft and J. Wyllie, The directed subg raphs homeo- morphism problem, Theoret. Comput. Sci., 10, 1980, 111–121

    work page 1980

  19. [19]

    Frank, T

    A. Frank, T. Kir´ aly and M. Kriesell, On decomposing a hy pergraph into k connected sub-hypergraphs, Discrete Appl. Math., 131, 200 3, 373–383

    work page

  20. [20]

    Georgiadis, R

    L. Georgiadis, R. E. Tarjan, Dominator tree certificati on and divergent spanning trees, ACM Trans. Algorithms, 12(1), 2015, Articl e 11, 42 pages

    work page 2015

  21. [21]

    Gr¨ otschel, A

    M. Gr¨ otschel, A. Martin, R. Weismantel, Packing Steiner trees: further facets, European J. Combin., 17, 1996, 39–52

    work page 1996

  22. [22]

    Gr¨ otschel, A

    M. Gr¨ otschel, A. Martin, R. Weismantel, Packing Stein er trees: poly- hedral investigations, Math. Program., 72, 1996, 101–123

    work page 1996

  23. [23]

    Gr¨ otschel, A

    M. Gr¨ otschel, A. Martin, R. Weismantel, Packing Stein er trees: a cut- ting plane algorithm and computational results, Math. Prog ram., 72, 1996, 125–145

    work page 1996

  24. [24]

    Gr¨ otschel, A

    M. Gr¨ otschel, A. Martin, R. Weismantel, Packing Stein er trees: sepa- ration algorithms, SIAM J. Discrete Math., 9, 1996, 233–257

    work page 1996

  25. [25]

    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

  26. [26]

    Guruswami, S

    V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd and M . Yan- nakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, J. Comput. Sy stem Sci., 67(3), 473–496, 2003

    work page 2003

  27. [27]

    Gutin and Y

    G. Gutin and Y. Sun, Arc-disjoint in- and out-branching s rooted at the same vertex in compositions of digraphs, Discrete Math., 34 3(5), 2020, 111816

    work page 2020

  28. [28]

    Hager, Pendant tree-connectivity, J

    M. Hager, Pendant tree-connectivity, J. Combin. Theor y Ser. B, 38, 1985, 179–189

    work page 1985

  29. [29]

    Hammack, Digraphs Products, in Classes of Directed Graphs (J

    R.H. Hammack, Digraphs Products, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018

    work page 2018

  30. [30]

    Huck, Disproof of a conjecture about independent bra nchings in k-connected directed graphs, J

    A. Huck, Disproof of a conjecture about independent bra nchings in k-connected directed graphs, J. Graph Theory, 20(2), 1995, 2 35–239

    work page 1995

  31. [31]

    Huck, Independent branchings in acyclic digraphs, D iscrete Math., 199, 1999, 245–249

    A. Huck, Independent branchings in acyclic digraphs, D iscrete Math., 199, 1999, 245–249. 31

    work page 1999

  32. [32]

    Huck, Independent trees and branchings in planar mul tigraphs, Graphs Combin., 15, 1999, 211–220

    A. Huck, Independent trees and branchings in planar mul tigraphs, Graphs Combin., 15, 1999, 211–220

    work page 1999

  33. [33]

    K. Jain, M. Mahdian and M.R. Salavatipour, Packing Stei ner trees, SODA, 2003, 266–274

    work page 2003

  34. [34]

    Jeong, K

    G.W. Jeong, K. Lee, S. Park and K. Park. A branch-and-pri ce algorithm for the Steiner tree packing problem, Comput. Oper. Res., 29 , 2002, 221–241

    work page 2002

  35. [35]

    Johnson, N

    T. Johnson, N. Robertson, P.D. Seymour and R. Thomas, Di rected tree-width, J. Combin. Theory Ser. B, 82(1), 2001, 138–154

    work page 2001

  36. [36]

    Kriesell, Edge-disjoint trees containing some give n vertices in a graph, J

    M. Kriesell, Edge-disjoint trees containing some give n vertices in a graph, J. Combin. Theory Ser. B, 88, 2003, 53–65

    work page 2003

  37. [37]

    Kriesell, Edge disjoint Steiner trees in graphs with out large bridges, J

    M. Kriesell, Edge disjoint Steiner trees in graphs with out large bridges, J. Graph Theory, 62, 2009, 188–198

    work page 2009

  38. [38]

    Kriesell, Packing Steiner trees on four terminals, J

    M. Kriesell, Packing Steiner trees on four terminals, J . Combin. Theory Ser. B, 100, 2010, 546–553

    work page 2010

  39. [39]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus, Linkedness and ordered cycles in digraphs. Combin. Probab. Comput., 17, 2008, 689–709

    work page 2008

  40. [40]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus, Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments, Adv. Ma th., 237, 2013, 62–146

    work page 2013

  41. [41]

    Lau, An approximate max-Steiner-tree-packing min- Steiner-cut the- orem, Combinatorica, 27, 2007, 71–90

    L. Lau, An approximate max-Steiner-tree-packing min- Steiner-cut the- orem, Combinatorica, 27, 2007, 71–90

    work page 2007

  42. [42]

    Li and Y

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

    work page 2016

  43. [43]

    X. Li, Y. Mao and Y. Sun, On the generalized (edge-)conne ctivity of graphs, Australas. J. Combin., 58(2), 2014, 304–319

    work page 2014

  44. [44]

    Lov´ asz, Coverings and colorings of hypergraphs, in: Proc

    L. Lov´ asz, Coverings and colorings of hypergraphs, in: Proc. 4th South- eastern Conf. on Comb., Utilitas Math., 1973, 3–12

    work page 1973

  45. [45]

    Nash-Williams, Edge-disjonint spanning tr ees of finite graphs, J

    C.St.J.A. Nash-Williams, Edge-disjonint spanning tr ees of finite graphs, J. London Math. Soc., 36, 1961, 445–450

    work page 1961

  46. [46]

    L.L. Ng. Hamiltonian decomposition of lexicographic p roducts of di- graphs, J. Combin. Theory Ser. B, 73(2), 1998, 119–129

    work page 1998

  47. [47]

    Pulleyblank, Two Steiner tree packing problems, S TOC, 1995, 383–387

    W.R. Pulleyblank, Two Steiner tree packing problems, S TOC, 1995, 383–387

    work page 1995

  48. [48]

    Robertson and P

    N. Robertson and P. Seymour, Graph minors XIII: The disj oint paths problem, J. Combin. Theory Ser. B, 63(1), 1995, 65–110

    work page 1995

  49. [49]

    Schrijver, Finding k partially disjoint paths in a directed planar graph, SIAM J

    A. Schrijver, Finding k partially disjoint paths in a directed planar graph, SIAM J. Comput., 23(4), 1994, 780–788. 32

    work page 1994

  50. [50]

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

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

    work page 1999

  51. [51]

    Steiglitz, P

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

    work page

  52. [52]

    Sun, Compositions of digraphs: a survey, arXiv:2103 .11171v1 [math.CO]

    Y. Sun, Compositions of digraphs: a survey, arXiv:2103 .11171v1 [math.CO]

    work page

  53. [53]

    Sun, Perfect out-forests and Steiner cycle packing i n digraphs, arXiv:2208.08618v2 [math.CO]

    Y. Sun, Perfect out-forests and Steiner cycle packing i n digraphs, arXiv:2208.08618v2 [math.CO]

    work page arXiv

  54. [54]

    Sun, Directed Steiner path packing and directed path connectivity, arXiv:2211.04025v3 [math.CO]

    Y. Sun, Directed Steiner path packing and directed path connectivity, arXiv:2211.04025v3 [math.CO]

    work page arXiv

  55. [55]

    Sun, Extremal results for directed tree connectivit y, Bull

    Y. Sun, Extremal results for directed tree connectivit y, Bull. Malays. Math. Sci. Soc., 45(2), 2022, 839–850

    work page 2022

  56. [56]

    Sun and G

    Y. Sun and G. Gutin, Strong subgraph connectivity of dig raphs: a survey, J. Interconnection Networks, 21(2), 2021, 2142004 (16 pages)

    work page 2021

  57. [57]

    Sun and G

    Y. Sun and G. Gutin, Strong subgraph connectivity of dig raphs, Graphs Combin., 37(3), 2021, 951–970

    work page 2021

  58. [58]

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

    work page 2019

  59. [59]

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

    work page 2019

  60. [60]

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

    work page 2022

  61. [61]

    Sun and Z

    Y. Sun and Z. Jin, Minimally strong subgraph ( k, ℓ )-arc-connected di- graphs, Discuss. Math. Graph Theory, 42(3), 2022, 759–770

    work page 2022

  62. [62]

    Sun and A

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

    work page 2023

  63. [63]

    Thomassen, Configurations in graphs of large minimum degree, con- nectivity, or chromatic number, Ann

    C. Thomassen, Configurations in graphs of large minimum degree, con- nectivity, or chromatic number, Ann. New York Acad. Sci., 55 5, 1989, 402–412

    work page 1989

  64. [64]

    Trotter, Jr

    W.T. Trotter, Jr. and P. Erd˝ os, When the Cartesian product of directed cycles is Hamiltonian, J. Graph Theory, 2(2), 1978, 137–142

    work page 1978

  65. [65]

    Tutte, On the problem of decomposing a graph into n connected factors, J

    W. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc., 36, 1961, 221–230

    work page 1961

  66. [66]

    Uchoa and M

    E. Uchoa and M. Poggi de Arag˜ ao, Vertex-disjoint packi ng of two Steiner trees: polyhedra and branch-and-cut, Math. Progra m., 90, 2001, 537–557. 33

    work page 2001

  67. [67]

    West and H

    D. West and H. Wu, Packing Steiner trees and S-connector s in graphs, J. Combin. Theory Ser. B, 102, 2012, 186–205

    work page 2012

  68. [68]

    R. W. Whitty, Vertex-disjoint paths and edge-disjoint branchings in directed graphs, J. Graph Theory, 11, 1997, 349–358. 34

    work page 1997