Pith. sign in

REVIEW 3 major objections 3 minor 64 references

Length-Constrained Network Design in Planar Digraphs

T0 review · 3 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read Length-constrained Directed Steiner Tree and Forest in planar digraphs admit (O(log k), O(log k))- and (O(log^6 k), O(log k))-bicriteria approximations, with only O(log k) slack in path length.

desk verdict Genuine new results for length-constrained planar DST/DSF, but the polynomial-time claims are currently conditional on an unproven FPTAS substitution for the NP-hard restricted shortest path oracle. read the letter →

arxiv 2607.25811 v1 pith:OWB37TBJ submitted 2026-07-28 cs.DS

Chandra Chekuri , Rhea Jain This is my paper · ORCID
classification cs.DS MSC 05C8568W2590C35
keywords length-constrainednetworkdesigndirectedSteinertreeforestplanardigraphsbicriteriaapproximationjunctiontreesseparatorsbuy-at-bulk
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

This paper asks whether network design problems that become harder when path lengths are bounded stay tractable in planar directed graphs. Its central claim is that they do: for the length-constrained versions of Directed Steiner Tree and Directed Steiner Forest, the authors give bicriteria approximation algorithms whose cost ratios match the best known for the unconstrained problems in planar digraphs, at the price of allowing paths to be longer than the bound by an O(log k) factor. The tree problem gets an (O(log k), O(log k)) approximation and an LP-competitive (O(log^2 k), O(log k)) version; the forest problem gets an (O(log^6 k), O(log k)) approximation. If these theorems are right, adding a length or delay limit to directed Steiner problems does not destroy the algorithmic advantage of planarity, and several related problems, including buy-at-bulk versions, inherit polylogarithmic approximations.

What carries the argument

Three structures carry the argument. First, the mixture metric, defined by c'(e)=c(e)+(γ/h)ℓ(e), blends edge cost and edge length into a true metric; a shortest path in this metric automatically has bounded cost and bounded length. Second, the planar separator lemma for directed paths, which guarantees three root-to-vertex dipaths whose removal splits the terminal set in half; the divide-and-conquer recursion follows exactly those paths. Third, for the forest result, the h-length-constrained junction tree: a subgraph rooted at a single vertex v in which each covered demand pair (s_i,t_i) is connected by an s_i-to-v path and a v-to-t_i path, each of length at most 3h. The paper proves low-den

What would settle it

Exhibit a planar LC-DST instance and a (1+epsilon)-approximate routine for d^(h)(s,t) such that substituting the approximation into the prune-and-separate step makes a separator path violate the cost/length bounds of Claim 3.2, pushing the solution's length slack beyond O(log k) or its cost beyond O(log k)·OPT. Alternatively, a family of planar LC-DST instances whose path-flow LP (LC-DST-LP) has integrality gap ω(log^2 k) would directly refute Theorem 1.2.

Watch

Extended reading notes

Core claim

The authors establish that the planar separator method, which already yields polylogarithmic approximations for Directed Steiner Tree and Forest in planar digraphs, can be made length-aware. The key move is to replace ordinary distances with a mixture metric c'(e)=c(e)+(γ/h)ℓ(e), which bakes the length bound into the cost used to find separator paths; the planar separator lemma then gives three paths from the root whose total cost is O(γ) and whose total length is O(h). Recursing over the components left by those separator paths yields the tree results: an O(log k)-approximation with O(log k) length slack, and an O(log^2 k) LP-competitive version when the LP optimum is used as the guess for

Load-bearing premise

The load-bearing algorithmic premise is that the cost of the cheapest path no longer than h between two vertices can be treated as exactly computable, even though computing it exactly is NP-hard and the paper only asserts, without proof, that an approximate version would do.

Editorial extensions

If this is right

  • LC-DST in planar digraphs has an (O(log k), O(log k))-bicriteria approximation, so demanding bounded-length paths costs only a logarithmic length violation over the unconstrained O(log k) ratio.
  • The natural path-flow LP relaxation for LC-DST is O(log^2 k)-competitive in planar digraphs, allowing the LP optimum to be used directly as a budget guide.
  • LC-DSF in planar digraphs has an (O(log^6 k), O(log k))-bicriteria approximation, giving the first length-constrained analogue of the planar forest result.
  • Buy-at-bulk versions of DST and DSF in planar digraphs inherit polylogarithmic approximations from the length-constrained algorithms, as the paper argues in its extensions section.
  • Length-constrained rooted group, covering, and polymatroid Steiner problems in planar digraphs also receive polylogarithmic approximations via the same recursion-tree embedding idea.

Reading between the lines

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

  • The O(log k) length slack appears tied to the recursion depth of the separator method: each level adds O(h) to path length. Whether the slack can be reduced to O(1) while keeping polylogarithmic cost, as has been done for length-constrained MST in undirected planar graphs, is a natural next question the paper leaves open.
  • The forest result's cost exponent (log^6 k) mirrors the gap between the tree and forest algorithms; an LP-competitive planar DSF, which the paper notes is unknown even without lengths, would immediately sharpen the forest ratio to roughly O(log^3 k).
  • The one-path lemma's 3h length bound and the 2h reachability windows along the central path suggest the true length slack of the forest construction may be improvable; layered examples where a demand path spans exactly three layers are the natural testbed for whether 3h is inherent.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper studies length-constrained versions of Directed Steiner Tree (LC-DST) and Directed Steiner Forest (LC-DSF) in planar digraphs, where edges have both costs and lengths and terminals must be connected by paths of length at most h. It claims a bicriteria (O(log k), O(log k))-approximation for LC-DST, an LP-competitive (O(log^2 k), O(log k)) approximation, and a bicriteria (O(log^6 k), O(log k))-approximation for LC-DSF. The technical approach adapts the planar separator framework of Friggstad–Mousavi for DST and the junction-tree framework of Chekuri–Jain for DSF, with a new one-path argument to handle length constraints. Theorems 1.1–1.3 are the central claims; if they hold, length-constrained directed Steiner problems inherit polylogarithmic approximability in planar digraphs.

Significance. If the results are correct, this is a meaningful contribution: it extends the recent line of polylogarithmic approximation algorithms for directed network design in planar digraphs to the length-constrained setting, with approximation ratios matching the best known for unconstrained DST and DSF and only an O(log k) length slack. The DSF result rests on a genuinely new argument in the one-path case (Lemma 4.7) that overcomes a non-metric obstacle in previous approaches. The paper carefully benchmarks against published separator and junction-tree theorems. However, a load-bearing algorithmic premise is left unproved: the exact NP-hard oracle d^(h) is assumed in Algorithm 2 and in the LP sections, and the asserted FPTAS substitution is not justified. Until this is repaired, the polynomial-time claims in Theorems 1.1–1.3 remain conditional. There is also a clear proof-writing error in Lemma 3.4 that needs correction.

major comments (3)
  1. [§3.1, Algorithm 2] The algorithms in §3.1 and §3.2 assume exact computation of the NP-hard quantity d^(h)(s,t). The parenthetical claim that replacing it with a (1+ε)-FPTAS 'does not affect the approximation guarantees' is unproved. With an approximate oracle d~∈[d,(1+ε)d], the infeasibility test 'if d^(h)(s,t)>γ' can falsely return Infeasible when d^(h)(s,t)=γ. The base case also requires an FPTAS with an explicit length/cost tradeoff. Lemmas 3.3, 3.4, and 3.6 must be re-derived with approximate distances; the threshold γ must be adjusted (e.g., to (1+ε)γ) and constants re-checked. The same issue appears in the dual-separation claim in §3.2 and in solving LC-Den-LP in §4.2. Since Theorems 1.1–1.3 rely on these polynomial-time subroutines, the polynomial-time guarantees are conditional without this proof.
  2. [§3.1, Lemma 3.4] The proof of Lemma 3.4 states the induction hypothesis as c(F) ≤ 12γ(log|S|+1), but in the F_2 branch it uses c(F_i) ≤ 12(log|S∩C_i|+1) OPT_i, which is not implied by the stated hypothesis. With the stated hypothesis the sum would be 12γ ∑ (log k_i+1), which is not ≤ 12γ log|S|. The argument is repaired by inducting on |S| with c(F) ≤ O(OPT log|S|), using ∑ OPT_i ≤ OPT. This is a local but load-bearing proof error that must be corrected.
  3. [§3.2, LC-DST-LP] The sentence 'The LP contains an exponential number of variables but can be solved approximately (up to a (1+ε) factor) via separation oracle on the dual' is not a proof. The dual separation problem is the NP-hard restricted shortest path problem; an approximate separation oracle is needed. The effect of approximate separation on the LP value and on the feasibility of the returned (x,f) solution—used in Lemma 3.5 and Lemma 3.6—is not analyzed. This is needed to make Theorem 1.2 rigorous and to support Theorem 1.3 via Lemma 4.12.
minor comments (3)
  1. [§4.1.1, Footnote 5] Claim 4.3 does not hold for j=0, as the authors note. The proposed dummy-vertex fix should be integrated into the proof of Lemma 4.2 rather than left as a footnote, since the current formal statement still claims the property for all j.
  2. [§1.1.1] The extensions to buy-at-bulk and rooted generalizations are deferred to the thesis [41]. Since they are not needed for the main theorems, please label them as informal or provide at least precise theorem statements.
  3. [§2.1] The preprocessing assumption 'all edge costs are ≥1 and polynomially bounded in n' is justified in one sentence. Please expand to make the (1+o(1)) loss precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reduction found; central proofs are modular and anchored in published external theorems, with non-circular correctness gaps flagged.

full rationale

I walked the claimed derivation chain. Theorems 1.1-1.3 are proved from external separator and planar-DST results (Thorup [58]; Friggstad-Mousavi [29]) and from the authors' own published planar-DSF / LP-DST papers [14,17]. Those citations are independent, published, externally checkable theorems, not the target results of the present paper; no quoted equation defines a predicted quantity in terms of the same fitted quantity. The mixture metric (Claim 2.1) is a standard metricization and is not used to define the target optimum into existence. The recursion in Algorithm 2 and h-frac-DST guesses costs and bounds them by induction; Lemmas 3.3-3.6 do not import Theorem 1.1 into Theorem 1.2. The LC-DSF proof (Lemmas 4.2, 4.4, 4.7, 4.12) combines a new one-path argument with published junction-tree machinery; the use of Theorem 1.2 inside Lemma 4.12 is intra-paper modularity, not circularity. The same-author citations are load-bearing but external and falsifiable, so under the stated rules they do not by themselves raise the circularity score. Two non-circular correctness gaps are flagged: (i) Sections 3.1-3.2 assert without proof that replacing exact d^(h) with a (1+epsilon)-approximation 'does not affect the approximation guarantees' and that the exponential LP 'can be solved approximately ... via separation oracle on the dual,' without analyzing the interaction with the recursion or the approximate separation oracle; and (ii) Footnote 5 admits Claim 4.3 'is not true when j=0' and asserts a dummy-vertex workaround without proof. These affect polynomial-time and feasibility claims, but they are not reductions of the derived results to their own inputs.

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

There are no fitted parameters in the paper: the guess gamma is an algorithmic parameter set to c(E) or an LP value, not a constant fitted to data. The mixture metric is a standard pre-existing tool, not a new invented entity. The main background commitments are the planar separator theorem, standard LP solvability, and prior published approximation results.

assumptions (5)
  • standard math Planar shortest-path separator theorem (Lipton–Tarjan/Thorup): every reachable planar digraph has three root-to-vertex dipaths whose removal halves terminal weight.
    Invoked as Lemma 1.4/2.2 in PruneAndSeparate and in the DSF reduction; proofs cited to [29,52,58], not re-derived.
  • domain assumption Restricted shortest path admits an FPTAS (Hassin) and can replace exact d^(h) without changing guarantees.
    Used throughout Algorithms 2 and h-frac-DST; the substitution claim is asserted but not proved in Section 3.1.
  • standard math The path-indexed LPs (LC-DST-LP, LC-Den-LP) are polynomial-time solvable up to (1+epsilon) via dual separation.
    Relied on for Theorems 1.2 and 4.16; no detailed separation proof is given.
  • domain assumption Published planar DST/DSF approximation results [29,17,14] are correct and can be used as black boxes.
    Theorems 1.1–1.3 build directly on these results; [14] and [17] are by the current authors but are published.
  • domain assumption The standard density/covering argument for junction-tree algorithms loses only O(log k).
    Used to convert low-density junction-tree existence into the full O(log^6 k) approximation in Theorem 1.3; not fully expanded.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Length-Constrained Network Design in Planar Digraphs." pith.science (2026). https://pith.science/paper/OWB37TBJ

@misc{pith2026260725811,
  author       = {Pith},
  title        = {Pith review of: Length-Constrained Network Design in Planar Digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OWB37TBJ}},
  note         = {Machine review of arXiv:2607.25811}
}
abstract

We study length-constrained generalizations of Directed Steiner Tree (DST) and Directed Steiner Forest (DSF) in planar digraphs. In both problems, the input is a directed graph with edge costs. DST asks for a min-cost subgraph connecting a root to a given set of terminals, and DSF asks for a min-cost subgraph connecting each of a given set of source-sink terminal pairs. In the length-constrained setting, each edge has both a cost and a length, and the input includes a length bound $h$; the goal is to find a min-cost subgraph connecting each terminal pair via a path of length at most $h$. Our work is motivated by a recent line of results showing that several network design problems that are traditionally hard in directed graphs admit polylogarithmic approximation ratios in planar digraphs. We give polylogarithmic bicriteria approximation algorithms for length-constrained analogues of DST and DSF in planar digraphs. Our approximation ratios match the best known for DST and DSF in planar digraphs, with an $O(\log k)$ violation of the length constraint, where $k$ denotes the number of terminals (or terminal pairs). As corollaries, we obtain polylogarithmic approximations for buy-at-bulk DST and DSF in planar digraphs.

Figures

Figures reproduced from arXiv: 2607.25811 by the authors.

Figure 1
Figure 1. This example assumes all edge lengths are [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. High-level overview of the divide-and-conquer algorithm. In Step 1, we compute the [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Consider the s-t path p shown in blue dashed lines; here the separator P is black and bolded. The portion of the path from u to t corresponds to p ′ . min X e∈E c(e)xe s.t. X p∈Ph t fp ≥ 1 ∀t ∈ S X p∈Ph t ,e∈p fp ≤ xe ∀e ∈ E, t ∈ S xe, fp ≥ 0 ∀e ∈ E, p ∈ ∪t∈SP h t (LC-DST-LP) The LP contains an exponential number of variables but can be solved approximately (up to a (1 + ϵ) factor) via separation oracle on the dual.… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example of graph in which s-t path spans 3 layers, L1, L2, L3. Claim 4.3. For each demand pair (si , ti) ∈ D, there exists j ∈ {0, . . . , q − 2} such that Gj \ {vj} contains an si-ti path of length at most h. Proof. Let Pi be an si-ti path of length at most h in G∗ ; …
Figure 5
Figure 5. Figure 5: Suppose ℓ(s1, v) = 1, ℓ(v, a′ 1 ) = h − 1, ℓ(s2, v) = h − 1, ℓ(v, a′ 2 ) = 1. The argument in [14] would re-route s2 to P via the path from v to a ′ 1 ; however, this would increase the length of the path from s2 to P to 2h − 2. In general, merging arbitrarily many ter…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 11 canonical work pages

  1. [14]

    A polylogarithmic approximation for Directed Steiner Forest in planar digraphs

    Chandra Chekuri and Rhea Jain. A polylogarithmic approximation for Directed Steiner Forest in planar digraphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2095–2110, 2025.doi:10.1137/1.9781611978322.67. 1, 1.2, 1.3, 4.1, 4.1, 1, 4.1.2, 4.1.3, 4.1.3, 5

    work page doi:10.1137/1.9781611978322.67 2025

  2. [17]

    From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs

    Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 ofLeibniz International Proceedings in Informatics (L...

    2024

  3. [1]

    Reachability preservers: New extremal bounds and approxi- mation algorithms.SIAM Journal on Computing, 53(2):221–246, 2024

    Amir Abboud and Greg Bodwin. Reachability preservers: New extremal bounds and approxi- mation algorithms.SIAM Journal on Computing, 53(2):221–246, 2024. 1.3

    2024

  4. [2]

    New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints.European Journal of Operational Research, 212(2):263–276, 2011

    Ibrahim Akgün and Barbaros Ç Tansel. New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints.European Journal of Operational Research, 212(2):263–276, 2011. 1.3

    2011

  5. [3]

    Ramos, and Mar- tin Skutella

    Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, and Mar- tin Skutella. Approximating k-hop minimum-spanning trees.Operations Research Letters, 33(2):115–120, 2005.doi:10.1016/j.orl.2004.05.005. 1.3

    doi:10.1016/j.orl.2004.05.005 2005

  6. [4]

    Buy-at-bulk network design with protection.Mathematics of Operations Research, 36(1):71–87, 2011.doi: 10.1287/moor.1110.0484

    Spyridon Antonakopoulos, Chandra Chekuri, Bruce Shepherd, and Lisa Zhang. Buy-at-bulk network design with protection.Mathematics of Operations Research, 36(1):71–87, 2011.doi: 10.1287/moor.1110.0484. 1.1.1

    arXiv 2011

  7. [5]

    Using a hop-constrained model to generate alternative communication network design.ORSA Journal on Computing, 4(2):192–205, 1992

    Anantaram Balakrishnan and Kemal Altinkemer. Using a hop-constrained model to generate alternative communication network design.ORSA Journal on Computing, 4(2):192–205, 1992. doi:10.1287/ijoc.4.2.192. 1.3

    doi:10.1287/ijoc.4.2.192 1992

  8. [6]

    Bateni, M

    M. Bateni, M. Hajiaghayi, and D. Marx. Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth.Journal of the ACM (JACM), 58(5):21, 2011. 1.3

    2011

Show all 64 references
  1. [7]

    Approximation algorithms for spanner problems and directed Steiner forest

    PiotrBerman, ArnabBhattacharyya, KonstantinMakarychev, SofyaRaskhodnikova, andGrig- ory Yaroslavtsev. Approximation algorithms for spanner problems and directed Steiner forest. Information and Computation, 222:93–107, 2013. 38th International Colloquium on Automata, Languages ...

    2013 doi

  2. [8]

    Near linear time(1 +ϵ)-approximation for restricted shortest paths in undi- rected graphs

    Aaron Bernstein. Near linear time(1 +ϵ)-approximation for restricted shortest paths in undi- rected graphs. InProceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 189–201. SIAM, 2012. 1.3

    2012

  3. [9]

    AnO(nlogn)approximation scheme for Steiner tree in planar graphs.ACM Transactions on Algorithms (TALG), 5(3):1–31, 2009

    Glencora Borradaile, Philip Klein, and Claire Mathieu. AnO(nlogn)approximation scheme for Steiner tree in planar graphs.ACM Transactions on Algorithms (TALG), 5(3):1–31, 2009. 1.3

    2009

  4. [10]

    Approximation algorithms for directed Steiner problems.Journal of Algorithms, 33(1):73–91, 1999

    Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed Steiner problems.Journal of Algorithms, 33(1):73–91, 1999. 1, 1.2, 1.3

    1999

  5. [11]

    Chekuri, M

    C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour. Approximation algorithms for nonuniform buy-at-bulk network design.SIAM Journal on Computing, 39(5):1772–1798, 2010.doi:10.1137/090750317. 1.1.1, 1.2, 1.3 22

    2010 doi

  6. [12]

    Set connectivity problems in undirected graphs and the directed steiner network problem.ACM Transactions on Algorithms (TALG), 7(2):1–17, 2011

    Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed steiner network problem.ACM Transactions on Algorithms (TALG), 7(2):1–17, 2011. 1, 1.3

    2011

  7. [13]

    Approximation algorithms for hop constrained and buy-at- bulk network design via hop constrained oblivious routing

    Chandra Chekuri and Rhea Jain. Approximation algorithms for hop constrained and buy-at- bulk network design via hop constrained oblivious routing. In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms (ESA 202...

    2024 doi

  8. [15]

    Node-weighted multicut in planar digraphs.arXiv preprint arXiv:2601.20038, 2026

    Chandra Chekuri and Rhea Jain. Node-weighted multicut in planar digraphs.arXiv preprint arXiv:2601.20038, 2026. 1.3

    2026

  9. [16]

    A polylogarithmic approximation for buy-at-bulk network design with protection

    Chandra Chekuri and Rhea Jain. A polylogarithmic approximation for buy-at-bulk network design with protection. InProceedings of the Fifty-Eighth Annual ACM Symposium on Theory of Computing (STOC), 2026. to be published. 1, 1.1.1

    2026

  10. [18]

    A recursive greedy algorithm for walks in directed graphs

    Chandra Chekuri and Martin Pal. A recursive greedy algorithm for walks in directed graphs. In 46th annual IEEE symposium on foundations of computer science (FOCS’05), pages 245–253. IEEE, 2005. 1.3

    2005

  11. [19]

    Approximating span- ners and directed steiner forest: Upper and lower bounds.ACM Transactions on Algorithms (TALG), 16(3):1–31, 2020

    Eden Chlamtáč, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. Approximating span- ners and directed steiner forest: Upper and lower bounds.ACM Transactions on Algorithms (TALG), 16(3):1–31, 2020. 1.3

    2020

  12. [20]

    Bypassing the surface embedding: approximation schemes for network design in minor-free graphs

    Vincent Cohen-Addad. Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 343–356, New York, NY, USA, June 2022. Association for Computing Machinery.d...

    2022

  13. [21]

    The 2-hop spanning tree problem.Operations Research Letters, 23(1):21–26, 1998

    Geir Dahl. The 2-hop spanning tree problem.Operations Research Letters, 23(1):21–26, 1998. doi:10.1016/S0167-6377(98)00029-7. 1.3

    1998 doi

  14. [22]

    Node-weighted Steiner tree and group Steiner tree in planar graphs.ACM Transactions on Algorithms (TALG), 10(3):1–20,

    Erik D Demaine, MohammadTaghi Hajiaghayi, and Philip N Klein. Node-weighted Steiner tree and group Steiner tree in planar graphs.ACM Transactions on Algorithms (TALG), 10(3):1–20,

  15. [23]

    Label cover instances with large girth and the hardness of approximating basic k-spanner.ACM Trans

    Michael Dinitz, Guy Kortsarz, and Ran Raz. Label cover instances with large girth and the hardness of approximating basic k-spanner.ACM Trans. Algorithms, 12(2), December 2016. doi:10.1145/2818375. 1.3

    2016 doi

  16. [24]

    Design networks with bounded pairwise distance

    Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In Proceedings of the thirty-first annual ACM Symposium on Theory of Computing (STOC), pages 750–759, 1999. URL:https://doi.org/10.1145/301250.301447. 1

    1999

  17. [25]

    Improved approximation algorithms for Directed Steiner Forest.Journal of Computer and System Sciences, 78(1):279–292, January

    Moran Feldman, Guy Kortsarz, and Zeev Nutov. Improved approximation algorithms for Directed Steiner Forest.Journal of Computer and System Sciences, 78(1):279–292, January

  18. [27]

    Linear programming hierarchies suffice for directed Steiner tree

    Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, and Madhur Tulsiani. Linear programming hierarchies suffice for directed Steiner tree. In International Conference on Integer Programming and Combinatorial Optimization, pages 285–

  19. [28]

    A constant-factor approximation for quasi-bipartite directed Steiner tree on minor-free graphs

    Zachary Friggstad and Ramin Mousavi. A constant-factor approximation for quasi-bipartite directed Steiner tree on minor-free graphs. InApproximation, Randomization, and Combinato- rial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), pages 13:1–13:18,

    2023

  20. [29]

    AO(logk)-Approximation for Directed Steiner Tree in Planar Graphs.ACM Transactions on Algorithms, 21(4):1–14, 2025

    Zachary Friggstad and Ramin Mousavi. AO(logk)-Approximation for Directed Steiner Tree in Planar Graphs.ACM Transactions on Algorithms, 21(4):1–14, 2025. Preliminary version in ICALP 2023. 1, 1.1.1, 1.2, 1.4, 1.2, 1.3, 3.1, 3.1

    2025

  21. [31]

    Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems.Mathematics of Operations Research, 47(2):1612–1630, 2022

    Rohan Ghuge and Viswanath Nagarajan. Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems.Mathematics of Operations Research, 47(2):1612–1630, 2022. 1, 1.3

    2022

  22. [32]

    Efficient computation of delay-sensitive routes from one source to all destinations

    Ashish Goel, Kajamalai G Ramakrishnan, Deepak Kataria, and Dimitris Logothetis. Efficient computation of delay-sensitive routes from one source to all destinations. InProceedings IEEE INFOCOM, volume 2, pages 854–858. IEEE, 2001. 1.3

    2001

  23. [33]

    Preliminary version in Proc

    Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li.O(log2 k/log logk)-approximation algo- rithm for directed Steiner tree: A tight quasi-polynomial time algorithm.SIAM Journal on Computing, 52(2):298–322, 2022. Preliminary version in Proc. of STOC 2019. 1, 1.3 24

    2022

  24. [34]

    Directed buy-at-bulk spanners

    Elena Grigorescu, Nithish Kumar, and Young-San Lin. Directed buy-at-bulk spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), pages 22–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    2025

  25. [35]

    Ellis Hershkowitz, and Goran Zuzic

    Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Tree embeddings for hop- constrained network design. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 356–369, New York, NY, USA, 2021. Association for Computing Machinery.d...

    2021

  26. [36]

    Approximating buy-at-bulk and shallow-lightk-steiner trees.Algorithmica, 53:89–103, 2009

    Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour. Approximating buy-at-bulk and shallow-lightk-steiner trees.Algorithmica, 53:89–103, 2009. 1.2, 1.3

    2009

  27. [37]

    Polylogarithmic inapproximability

    Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 585–594, 2003. 1

    2003

  28. [38]

    Approximation schemes for the restricted shortest path problem.Mathematics of Operations research, 17(1):36–42, 1992

    Refael Hassin. Approximation schemes for the restricted shortest path problem.Mathematics of Operations research, 17(1):36–42, 1992. 1.3, 2.2

    1992

  29. [39]

    Planar length-constrained minimum spanning trees

    D Ellis Hershkowitz and Richard Z Huang. Planar length-constrained minimum spanning trees. arXiv preprint arXiv:2510.09002, 2025. To appear in STOC 2026. 1, 1.1, 1.2

    2025

  30. [40]

    Simple length-constrained minimum spanning trees

    D Ellis Hershkowitz and Richard Z Huang. Simple length-constrained minimum spanning trees. In2025 Symposium on Simplicity in Algorithms (SOSA), pages 341–349, 2025. URL:https:// epubs.siam.org/doi/abs/10.1137/1.9781611978315.25,arXiv:https://epubs.siam.org/ doi/pdf/10.1137/1.9...

    2025 doi

  31. [41]

    University of Illinois at Urbana-Champaign, 2026

    Rhea Jain.Approximation Algorithms for Connectivity and Fault-Tolerant Network Design. University of Illinois at Urbana-Champaign, 2026. 1.1.1

    2026

  32. [42]

    WH Freeman, 1979

    David S Johnson and Michael R Garey.Computers and intractability: A guide to the theory of NP-completeness. WH Freeman, 1979. 1.3, 2.2

    1979

  33. [43]

    The shortest route problem with constraints.Journal of Mathematical analysis and applications, 14(2):191–197, 1966

    Hans C Joksch. The shortest route problem with constraints.Journal of Mathematical analysis and applications, 14(2):191–197, 1966. 1.3

    1966

  34. [44]

    Approximate hierarchical facility location and applications to the shallow steiner tree and range assignment problems

    Erez Kantor and David Peleg. Approximate hierarchical facility location and applications to the shallow steiner tree and range assignment problems. In Tiziana Calamoneri, Irene Finocchi, and Giuseppe F. Italiano, editors,Algorithms and Complexity, pages 211–222, Berlin, Heidelberg,

  35. [45]

    Embeddings of planar quasimetrics into directedℓ 1 and polylogarithmic approximation for directed sparsest-cut

    Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of planar quasimetrics into directedℓ 1 and polylogarithmic approximation for directed sparsest-cut. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022,...

    2021

  36. [46]

    Reza Khani and Mohammad R

    M. Reza Khani and Mohammad R. Salavatipour. Improved approximations for buy-at-bulk and shallow-lightk-steiner trees and(k,2)-subgraph.J. Comb. Optim., 31(2):669–685, February 2016.doi:10.1007/s10878-014-9774-5. 1.3

    2016 doi

  37. [47]

    Approximating the degree-bounded min- imum diameter spanning tree problem.Algorithmica, 41:117–129, 2005

    Jochen Könemann, Asaf Levin, and Amitabh Sinha. Approximating the degree-bounded min- imum diameter spanning tree problem.Algorithmica, 41:117–129, 2005. 1.3 25

    2005

  38. [48]

    Approximating some network design problems with node costs

    Guy Kortsarz and Zeev Nutov. Approximating some network design problems with node costs. Theoretical Computer Science, 412(35):4482–4492, 2011. URL:https://www.sciencedirect. com/science/article/pii/S0304397511003021,doi:10.1016/j.tcs.2011.04.013. 1.3

    2011 doi

  39. [49]

    Approximating shallow-light trees

    Guy Kortsarz and David Peleg. Approximating shallow-light trees. InProceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97, page 103–110, USA, 1997. Society for Industrial and Applied Mathematics. 1.3

    1997

  40. [50]

    On the integrality gap of directed Steiner tree LPs with relatively integral solutions.arXiv preprint arXiv:2412.10744, 2024

    Bundit Laekhanukit. On the integrality gap of directed Steiner tree LPs with relatively integral solutions.arXiv preprint arXiv:2412.10744, 2024. 1.3

    2024

  41. [51]

    Polynomial integrality gap of flow LP for directed Steiner tree

    Shi Li and Bundit Laekhanukit. Polynomial integrality gap of flow LP for directed Steiner tree. ACM Transactions on Algorithms, 21(1):1–9, 2024. 1, 1.3

    2024

  42. [52]

    Lipton and Robert Endre Tarjan

    Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.arXiv:https://doi.org/10.1137/ 0136016,doi:10.1137/0136016. 2.3, 2.2

    1979 doi

  43. [53]

    A simple efficient approximation scheme for the restricted shortest path problem.Operations Research Letters, 28(5):213–219, 2001

    Dean H Lorenz and Danny Raz. A simple efficient approximation scheme for the restricted shortest path problem.Operations Research Letters, 28(5):213–219, 2001. 1.3

    2001

  44. [54]

    Bicriteria network design problems.Journal of Algorithms, 28(1):142–171,

    Madhav V Marathe, R Ravi, Ravi Sundaram, S.S Ravi, Daniel J Rosenkrantz, and Harry B Hunt. Bicriteria network design problems.Journal of Algorithms, 28(1):142–171,

  45. [55]

    New formulations and solution procedures for the hop con- strained network design problem.European Journal of Operational Research, 148(1):126–140,

    Hasan Pirkul and Samit Soni. New formulations and solution procedures for the hop con- strained network design problem.European Journal of Operational Research, 148(1):126–140,

  46. [56]

    Rapidrumorramification: approximatingtheminimumbroadcasttime

    R.Ravi. Rapidrumorramification: approximatingtheminimumbroadcasttime. InProceedings 35th Annual Symposium on Foundations of Computer Science, pages 202–213, 1994.doi: 10.1109/SFCS.1994.365693. 1.3

    1994

  47. [58]

    Compact oracles for reachability and approximate distances in planar digraphs

    Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993–1024, November 2004.doi:10.1145/1039488.1039493. 1.4, 1.3, 2.3, 2.2, 4.1

    2004

  48. [59]

    Approximation of pareto optima in multiple-objective, shortest-path prob- lems.Operations research, 35(1):70–79, 1987

    Arthur Warburton. Approximation of pareto optima in multiple-objective, shortest-path prob- lems.Operations research, 35(1):70–79, 1987. 1.3

    1987

  49. [60]

    A series of approximation algorithms for the acyclic directed Steiner tree problem.Algorithmica, 18(1):99–110, 1997

    Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem.Algorithmica, 18(1):99–110, 1997. 1, 1.3

    1997

  50. [61]

    On directed Steiner trees

    Leonid Zosin and Samir Khuller. On directed Steiner trees. InProceedings of ACM-SIAM SODA, pages 59–63, 2002. 1, 1.3 26

    2002

  51. [1998]

    URL:https://www.sciencedirect.com/science/article/pii/S0196677498909300, doi:10.1006/jagm.1998.0930. 1.3

    1998

  52. [2003]

    URL:https://www.sciencedirect.com/science/article/pii/S0377221702003661, doi:10.1016/S0377-2217(02)00366-1. 1.3

    doi

  53. [2006]

    Springer Berlin Heidelberg. 1.3

  54. [2011]

    URL:http://arxiv.org/abs/1111.5473,arXiv:1111.5473. 1.3

    arXiv

  55. [2012]

    URL:https://www.sciencedirect.com/science/article/pii/S0022000011000584, doi:10.1016/j.jcss.2011.05.009. 1.3

    2011 doi

  56. [2023]

    URL:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/ RANDOM.2023.13,doi:10.4230/LIPIcs.APPROX/RANDOM.2023.13. 1.3

    2023 doi

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.