Pith. sign in

REVIEW 1 major objections 69 references

Problems related to strong connectivity and strong biconnectivity

T0 review · 1 major / 0 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read There exists a polynomial-time 7-approximation algorithm for the minimum-edge subset problem that preserves strong biconnectivity and strong connectivity after any single vertex removal from B.

desk verdict The paper defines a constrained strong biconnectivity problem with an auxiliary set B and claims a 7-approximation, but the provided text gives no algorithm or analysis to support it. read the letter →

arxiv 2606.16087 v2 pith:EFHGO47C submitted 2026-06-15 cs.DS

Raed Jaberi This is my paper · ORCID
classification cs.DS
keywords strongconnectivitybiconnectivityapproximationalgorithmdirectedgraphsedgesubsetselectionvertexdeletion
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies the problem of finding a smallest subset of edges E_beta in a strongly biconnected directed graph G so that the subgraph on those edges stays strongly biconnected and, for every vertex w in a given set B, stays strongly connected after deleting w. It establishes that a polynomial-time algorithm exists whose output is guaranteed to be at most seven times larger than the optimal solution size. A reader would care because the result supplies a concrete, efficient way to sparsify directed graphs while protecting against single-vertex failures under the stated precondition on B. The work focuses on extending connectivity-preservation questions by adding the extra constraint for vertices in B.

What carries the argument

The 7-approximation algorithm that selects a minimum-size edge subset preserving the two strong-connectivity conditions under the B-vertex constraint.

What would settle it

An input graph meeting the preconditions together with an explicit run of the algorithm whose output size exceeds seven times the size of the true minimum edge subset.

Watch

Extended reading notes

Core claim

We prove that there exists a polynomial time 7-approximation algorithm for computing a minimum size subset E_beta of edges such that the subgraph G_beta is strongly biconnected and for each vertex w in B the subgraph G_beta without w is strongly connected, when the input graph meets the strong-biconnectivity and B-removal preconditions.

Load-bearing premise

The input graph is strongly biconnected and remains strongly connected after the removal of any single vertex from the set B.

Editorial extensions

If this is right

  • The algorithm runs in polynomial time on any qualifying input.
  • Any optimal solution is at most one-seventh the size of the solution returned by the algorithm.
  • The output subgraph satisfies strong biconnectivity for the whole vertex set.
  • The output subgraph satisfies strong connectivity after deleting any vertex from B.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the 7-approximation can be tightened, the same proof structure might yield better ratios for related directed connectivity problems.
  • The precondition that G minus any w in B stays strongly connected is essential; without it the problem statement itself may become ill-posed.
  • The result suggests that similar approximation techniques could apply to undirected biconnectivity versions of the same edge-subset task.
Share X Bluesky LinkedIn Reddit HN

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

1 major / 0 minor

Summary. The manuscript defines a problem on a strongly biconnected digraph G=(V,E) together with a vertex set B where G-w remains strongly connected for every w in B. The task is to compute a minimum-size edge subset E_β such that the spanning subgraph G_β=(V,E_β) is strongly biconnected and G_β-w remains strongly connected for every w in B. The sole result asserted is the existence of a polynomial-time 7-approximation algorithm for this problem.

Significance. A correct 7-approximation for this edge-minimization problem under the stated connectivity preconditions would constitute a modest but concrete contribution to the literature on approximation algorithms for strong-connectivity augmentation and survivable network design. No machine-checked proofs, reproducible code, or parameter-free closed-form derivations are supplied.

major comments (1)
  1. [Abstract] Abstract (and entire provided manuscript text): the central claim that a polynomial-time 7-approximation algorithm exists is stated without any proof sketch, reduction, algorithm description, or ratio analysis. Consequently the data and reasoning supplied do not support the claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. The sole major comment correctly identifies that the provided manuscript text states the 7-approximation claim without supporting technical details. We address this point below and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and entire provided manuscript text): the central claim that a polynomial-time 7-approximation algorithm exists is stated without any proof sketch, reduction, algorithm description, or ratio analysis. Consequently the data and reasoning supplied do not support the claim.

    Authors: We agree with this observation. The manuscript excerpt supplied to the referee contains only the problem definition and the assertion of a polynomial-time 7-approximation algorithm, without any algorithm description, proof sketch, or ratio analysis. This is a substantive gap. In the revised manuscript we will add a complete description of the algorithm (including any reductions or constructions), a proof of correctness, and the analysis establishing the approximation ratio of 7. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The manuscript claims existence of a polynomial-time 7-approximation algorithm for the stated minimum-size E_β problem on strongly biconnected graphs satisfying the given precondition on B. This is an algorithmic existence result whose proof is internal to the paper; no equations, fitted parameters, self-definitional reductions, or load-bearing self-citations appear that would collapse the claimed result back onto its inputs by construction. The derivation chain is therefore self-contained.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The paper introduces no free parameters, no new entities, and relies only on the standard definition of strong connectivity and biconnectivity in directed graphs.

assumptions (1)
  • domain assumption The input is a directed graph G that is strongly biconnected and satisfies the removal condition for every w in B
    Explicitly stated as the setting in which the problem is defined.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Problems related to strong connectivity and strong biconnectivity." pith.science (2026). https://pith.science/paper/EFHGO47C

@misc{pith2026260616087,
  author       = {Pith},
  title        = {Pith review of: Problems related to strong connectivity and strong biconnectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EFHGO47C}},
  note         = {Machine review of arXiv:2606.16087}
}
abstract

Let $G=(V,E)$ be a strong biconnected graph and let $B \subseteq V$ such that for each vertex $w \in B$, the subgraph $G \setminus \lbrace w\rbrace$ is strongly connected. In this paper we study the problem of computing a subset $E_{\beta} \subseteq E$ of minimum size such that the subgraph $G_{\beta}=(V,E_{\beta})$ is strongly biconnected and for each vertex $w \in B$, the subgraph $G_{\beta} \setminus \lbrace w\rbrace$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.

Figures

Figures reproduced from arXiv: 2606.16087 by the authors.

Figure 1
Figure 1. (a) Each vertex in V \ {3, 9, 6} is a strong articulation point. (b) An optimal solution for minimum strongly connected spanning subgraph problem with same strong articulation points. (c) An optimal solution for MBSC when B = {9}. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. (a) Each vertex in V \{3, 9} is a strong articulation point. (b) An optimal solution for minimum strongly connected spanning subgraph problem.(c) An optimal solution when B = {3}. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 12 canonical work pages

  1. [1]

    Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1999). Data structures and algorithms. Addison-Wesley series in computer sci- ence and information processing (Repr. with corrections ed.). Reading, Mass.: Addison-Wesley. ISBN 978-0-201-00023-8

    1999

  2. [2]

    Alstrup, D

    S. Alstrup, D. Harel, P.W. Lauridsen, M. Thorup, Dominators in linear time, SIAM J. Comput. 28(6) (1999) 2117–2132

    1999

  3. [3]

    Buchsbaum, L

    A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan, J.R. Westbrook, Linear-time algorithms for dominators and other path- evaluation problems, SIAM J. Comput. 38(4) (2008) 1533–1573. 8

    2008

  4. [4]

    U. Brandes. Eager st-Ordering. In Proceedings of the 10th European Symposium of Algorithms (ESA’02), pages 247–256, 2002

    2002

  5. [5]

    Adi Botea, Davide Bonusi, Pavel Surynek: Solving Multi-agent Path Finding on Strongly Biconnected Digraphs. J. Artif. Intell. Res.62 : 273–314(2018)

    2018

  6. [6]

    IJCAI 5563–5567(2018)

    Adi Botea, Davide Bonusi, Pavel Surynek: Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract). IJCAI 5563–5567(2018)

    2018

  7. [7]

    AAAI 2015 : 2024–2030

    Adi Botea, Pavel Surynek: Multi-Agent Path Finding on Strongly Bi- connected Digraphs. AAAI 2015 : 2024–2030

    2015

  8. [8]

    Buchsbaum, L

    A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan, J.R. Westbrook, Linear-time algorithms for dominators and other path- evaluation problems, SIAM J. Comput. 38(4) (2008) 1533–1573

    2008

Show all 69 references
  1. [9]

    Algorithmica 15(6): 521– 549(1996)

    Joseph Cheriyan, Kurt Mehlhorn: Algorithms for Dense Graphs and Networks on the Random Access Computer. Algorithmica 15(6): 521– 549(1996)

    1996

  2. [10]

    Cheriyan, R

    J. Cheriyan, R. Thurimella, Approximating Minimum-Sizek- Connected Spanning Subgraphs via Matching. SIAM J. Comput. 30(2): 528–560 (2000)

    2000

  3. [11]

    Johannes Carmesin, Reinhard Diestel, Matthias Hamann, Fabian Hun- dertmark: k-Blocks: A Connectivity Invariant for Graphs. SIAM J. Discret. Math. 28(4): 1876-1891 (2014)

    2014

  4. [12]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed. Cambridge: The MIT Press, 2022

    2022

  5. [13]

    Italiano, Veronika Loitzenbauer, and Nikos Parotsidis

    Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for com- puting maximal 2-connected subgraphs in sparse directed graphs. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms, (SODA 2017), pages 1900–1918, 2017

    2017

  6. [14]

    Dahiphale, ”MapReduce for Graphs Processing: New Big Data Algorithm for 2-Edge Connected Components and Future Ideas,” in IEEE Access, vol

    D. Dahiphale, ”MapReduce for Graphs Processing: New Big Data Algorithm for 2-Edge Connected Components and Future Ideas,” in IEEE Access, vol. 11, pp. 54986-55001, 2023, doi: 10.1109/AC- CESS.2023.3281266

    2023 doi

  7. [15]

    Y. M. Erusalimskii and G. G. Svetlov. Bijoin points, bibridges, and biblocks of directed graphs. Cybernetics and Systems Analysis, 16(1):41–44, 1980. 9

    1980

  8. [16]

    Edmonds, Edge-disjoint branchings

    J. Edmonds, Edge-disjoint branchings. Combinatorial Algorithms, pages 91–96, 1972

    1972

  9. [17]

    J. Ebert. st-Ordering the vertices of biconnected graphs. Computing, 30:19–33, 1983

    1983

  10. [18]

    Italiano, Luigi Laura, Federico Santaroni: Strong Articulation Points and Strong Bridges in Large Scale Graphs

    Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Federico Santaroni: Strong Articulation Points and Strong Bridges in Large Scale Graphs. Algorithmica 74(3): 1123–1147(2016)

    2016

  11. [19]

    M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0–7167– 1044–7

    1979

  12. [20]

    Gabow: Path-based depth-first search for strong and bicon- nected components

    Harold N. Gabow: Path-based depth-first search for strong and bicon- nected components. Inf. Process. Lett. 74(3-4): 107-114 (2000)

    2000

  13. [21]

    Georgiadis, Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In Proc

    L. Georgiadis, Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In Proc. 37th ICALP, Part I, LNCS 6198 (2010) 738–749

    2010

  14. [22]

    In: Proc

    Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex- disjoint paths. In: Proc. 16th ACM-SIAM Symp. on Discrete Algo- rithms, pp. 433–442(2005)

    2005

  15. [23]

    Georgiadis: Approximating the Smallest 2-Vertex Connected Span- ning Subgraph of a Directed Graph

    L. Georgiadis: Approximating the Smallest 2-Vertex Connected Span- ning Subgraph of a Directed Graph. ESA 2011 : 13–24

    2011

  16. [24]

    Georgiadis, G.F

    L. Georgiadis, G.F. Italiano, C. Papadopoulos, N. Parotsidis, Approx- imating the smallest spanning subgraph for 2-edge-connectivity in di- rected graphs, in: Proc. 23rd European Symposium on Algorithms, 2015, pp.582–594

    2015

  17. [25]

    ISAAC 2020 38 : 1–38 : 16

    Loukas Georgiadis, Evangelos Kosinas, Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. ISAAC 2020 38 : 1–38 : 16

    2020

  18. [26]

    Tarjan, Dominator Tree Certification and Divergent Spanning Trees

    Loukas Georgiadis, Robert E. Tarjan, Dominator Tree Certification and Divergent Spanning Trees. ACM Trans. Algorithms 12(1) : 11 : 1– 11 : 42(2016)

    2016

  19. [27]

    Georgiadis, G

    L. Georgiadis, G. F. Italiano, A. Karanasiou: Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Or- ders,”Proc.16th International Symposium on Experimental Algorithms, pp.9:1-9:16, 2017

    2017

  20. [28]

    Georgiadis, G

    L. Georgiadis, G. F. Italiano, A. Karanasiou: Approximating the small- est 2-vertex connected spanning subgraph of a directed graph. Theor. Comput. Sci. 807: 185–200(2020) 10

    2020

  21. [29]

    Georgiadis, G.F

    L. Georgiadis, G.F. Italiano, L. Laura, N. Parotsidis, 2-Edge Connec- tivity in Directed Graphs, SODA (2015) 1988–2005

    2015

  22. [30]

    Georgiadis, G

    L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis, 2-Edge Con- nectivity in Directed Graphs. ACM Trans. Algorithms 13(1) : 9 : 1– 9 : 24(2016)

    2016

  23. [31]

    Georgiadis, G.F

    L. Georgiadis, G.F. Italiano, L. Laura, N. Parotsidis, 2-Vertex Connec- tivity in Directed Graphs, ICALP (1)2015 : 605–616

    2015

  24. [32]

    Georgiadis, G

    L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis, 2-vertex connec- tivity in directed graphs. Inf. Comput. 261 : 248–264(2018)

    2018

  25. [33]

    Georgiadis, G

    L. Georgiadis, G. F. Italiano, A. Karanasiou, N. Parotsidis, N. Paudel, Computing 2-Connected Components and Maximal 2-Connected Sub- graphs in Directed Graphs: An Experimental Study. ALENEX 2018 : 169–183

    2018

  26. [34]

    Linear-Time Algo- rithms for Computing Twinless Strong Articulation Points and Related Problems

    Loukas Georgiadis and Evangelos Kosinas. Linear-Time Algo- rithms for Computing Twinless Strong Articulation Points and Related Problems. In 31st International Symposium on Algo- rithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Vo...

    2020 doi

  27. [35]

    Olivier Durand de Gevigney, Zolt´ an Szigeti: On minimally 2-T- connected directed graphs. Discret. Appl. Math. 250 : 183–185(2018)

    2018

  28. [36]

    ICALP (1) 2015: 713–724

    Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer: Find- ing 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. ICALP (1) 2015: 713–724

    2015

  29. [37]

    Italiano, L

    G.F. Italiano, L. Laura, F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science 447 (2012) 74–84

    2012

  30. [38]

    G. F. Italiano, L. Laura, F. Santaroni, Finding Strong Bridges and Strong Articulation Points in Linear Time. COCOA (1)2010 : 157–169

    2010

  31. [39]

    CoRR abs/2207.04321 (2022)

    Raed Jaberi, Minimum strongly biconnected spanning directed sub- graph problem. CoRR abs/2207.04321 (2022)

    2022

  32. [40]

    Discrete Applied Mathematics 204: (2016)164–172

    Raed Jaberi, On computing the 2-vertex-connected components of di- rected graphs. Discrete Applied Mathematics 204: (2016)164–172

    2016

  33. [41]

    RAIRO - Theor

    Raed Jaberi, Computing the 2-blocks of directed graphs. RAIRO - Theor. Inf. and Applic. 49(2)(2015)93–119 11

    2015

  34. [42]

    Raed Jaberi, 2-edge-twinless blocks, Bulletin des Sciences Math´ ematiques, Volume 168, 102969, ISSN 0007–4497, (2021), https://doi.org/10.1016/j.bulsci.2021.102969

    2021 doi

  35. [43]

    Raed Jaberi, Computing 2-twinless blocks, Discrete Mathematics Let- ters, 29–33, Volume 5(2021), DOI: 10.47443/dml.2020.0037

    2021 doi

  36. [44]

    Raed Jaberi, Minimum 2-Vertex Strongly Biconnected Spanning Di- rected Subgraph Problem Discrete Mathematics Letters, 40–43, Volume 7(2021) DOI: 10.47443/dml.2021.0024

    2021 doi

  37. [45]

    CoRR abs/1912.11799 (2019)

    Raed Jaberi, Twinless articulation points and some related problems. CoRR abs/1912.11799 (2019)

    1912

  38. [46]

    CoRR abs/2007.01897 (2020)

    Raed Jaberi, b-articulation points and b-bridges in strongly biconnected directed graphs. CoRR abs/2007.01897 (2020)

    2007

  39. [47]

    CoRR abs/2007.09793 (2020)

    Raed Jaberi, 2-blocks in strongly biconnected directed graphs. CoRR abs/2007.09793 (2020)

    2007

  40. [48]

    CoRR abs/2001.03788 (2020)

    Raed Jaberi, Minimum 2-vertex-twinless connected spanning subgraph problem. CoRR abs/2001.03788 (2020)

    2001

  41. [49]

    Raed Jaberi, Minimum 2-edge strongly biconnected spanning directed subgraph problem, CoRR abs/2207.03401 (2022)

    2022

  42. [50]

    Raed Jaberi, Reham Mansour, An experimental study of algorithms for identifying approximate solutions for minimum 2-T connected spanning subgraph problem, Homs University Journal 2026

    2026

  43. [51]

    Khuller, B

    S. Khuller, B. Raghavachari, N.E. Young, Approximating the Minimum Equivalent Diagraph. SODA (1994) 177–186

    1994

  44. [52]

    Lengauer, R.E

    T. Lengauer, R.E. Tarjan, A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1(1) (1979) 121–141

    1979

  45. [53]

    Esko Nuutila, Eljas Soisalon-Soininen: On Finding the Strongly Con- nected Components in a Directed Graph, Inf. Process. Lett. 49(1) : 9– 14(1994)

    1994

  46. [54]

    Mader, Minimaln-fach zusammenh ¨angende Digraphen

    W. Mader, Minimaln-fach zusammenh ¨angende Digraphen. J. Comb. Theory, Ser. B 38(2) : 102–117(1985)

    1985

  47. [55]

    Makino An algorithm for finding all the k-components of a digraph Int

    S. Makino An algorithm for finding all the k-components of a digraph Int. J. Comput. Math., 24 (3–4) (1988), pp. 213-221

    1988

  48. [56]

    Mader, A reduction method for edge-connectivity in graphs, Ann

    W. Mader, A reduction method for edge-connectivity in graphs, Ann. Disc. Math. (1978)145–164 12

    1978

  49. [57]

    Mader, On vertices of outdegree n in minimally n-connected di- graphs, J

    W. Mader, On vertices of outdegree n in minimally n-connected di- graphs, J. Graph Theory 39(2)(2002)129–144

    2002

  50. [58]

    Menger, Karl, ”Zur allgemeinen Kurventheorie”. Fund. Math. (1927)10 : 96–115. doi:10.4064/fm-10-1-96-115

    1927 doi

  51. [59]

    Pearce: A space-efficient algorithm for finding strongly con- nected components, Inf

    David J. Pearce: A space-efficient algorithm for finding strongly con- nected components, Inf. Process. Lett., 116(1)47–52(2016)

    2016

  52. [60]

    Springer 2019, ISBN 978-3-030-25208-3, page 292

    Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Demen- tiev: Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer 2019, ISBN 978-3-030-25208-3, page 292

    2019

  53. [61]

    Reif, P.G

    J.H. Reif, P.G. Spirakis Strong k-Connectivity in Digraphs and Random Digraphs, Technical Report TR-25–81 Harvard University (1981)

    1981

  54. [62]

    Raghavan, Twinless Strongly Connected Components, Perspectives in Operations Research, (2006) 285–304

    S. Raghavan, Twinless Strongly Connected Components, Perspectives in Operations Research, (2006) 285–304

    2006

  55. [63]

    Schmidt: A simple test on 2-vertex- and 2-edge-connectivity

    Jens M. Schmidt: A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett. 113(7) : 241-244(2013)

    2013

  56. [64]

    M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers and Mathematics with Applications, 7(1) : 67–72,(1981)

    1981

  57. [65]

    R. E. Tarjan, Depth First Search and Linear Graph Algorithms, SIAM J. Comput.,1(2)(1972),146–160

    1972

  58. [66]

    R. E. Tarjan. A note on finding the bridges of a graph. Information Processing Letters, 2(6):160–161, 1974

    1974

  59. [67]

    SODA 417–426(2001)

    Adrian Vetta: Approximating the minimum strongly connected sub- graph via a matching lower bound. SODA 417–426(2001)

    2001

  60. [68]

    Z. Wu, S. Grumbach, Feasibility of motion planning on acyclic and strongly connected directed graphs. Discret. Appl. Math. 158(9) : 1017– 1028(2010)

    2010

  61. [69]

    L. Zhao, H. Nagamochi, T. Ibaraki, A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem, Inf. Process. Lett. 86 (2003) 63–70. 13

    2003

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.