Pith.

Data Structures and Algorithms · arXiv:2611.17201 v1 · submitted 12 Nov 2026 · 46 references

A Little Length Slack Goes a Long Way in Planar Length-Constrained Network Design

D Ellis Hershkowitz, Richard Z Huang, Rhea Jain, Manas Korimilli

The paper says

“Problems in length-constrained network design ask for min-cost subgraphs connecting k input vertex pairs by paths of length at most h.”

more of the abstract

Algorithms that instead connect these pairs by paths of length at most βh are said to have length slack β. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack 1 + ε and approximation ratios of O(log2k/ε) for directed Steiner tree and O(log5k/ε2) for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an O(log6k/ε) approximation on planar graphs with length slack 6 + ε. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below 3.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions. Serious theory paper that likely resolves the stated O(1)-slack open questions; the LC-DST pipeline is clean and checkable, while LC-SF is the dense part a referee must actually sit with. This line is wrong

4 major objections · 7 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 46 references say.

The paper says, at §4.2, Lemma 4.7 and surrounding text

The review did not quote this passage.

Pith says: Objection 1 of 4 · major

The bound on the number of chunks containing a given vertex is O(log^2 k/(ε log τ)). However, the derivation of the O(1/ε) factor per separator path relies on Lemma 4.3, which states that every path in bucket B_j has mixture cost at most 2γ_j.

more of objection 1

Lemma 4.3 itself depends on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions γ_j = (X/k) τ^j are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in B_j, potentially increasing the number of chunks per vertex beyond O(1/ε). The authors acknowledge the scaling (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This could affect the O(log^5 k/ε^2) approximation ratio for LC-SF. The authors should clarify whether the bucket definitions are adjusted after scaling, or provide a justification that the bound remains valid.

The paper says, at §4.2, Lemma 4.8

The review did not quote this passage.

Pith says: Objection 2 of 4 · major

The proof of Lemma 4.8 states that 'the recursive process continues until all terminal pairs are separated, therefore every path in P_hi must intersect the separator at some level of recursion.' However, the recursion is on the graph after removing separator paths, and the separator paths are defined with respect to an arbitrary root r.

more of objection 2

It is not guaranteed that every s_i-t_i path in the LP support intersects the separator at some level, because the separator is defined from a fixed root r, not from the terminal pairs. The recursion only separates terminals that lie in different components after removing the separator paths, but a path could potentially avoid all separator paths if it stays entirely within a component that is never separated. The authors should justify that the separator hierarchy eventually separates all terminal pairs, or adjust the argument to account for paths that may not intersect any separator.

The paper says, at §3.2, Lemma 3.9

The review did not quote this passage.

Pith says: Objection 3 of 4 · major

The proof of Lemma 3.9 charges the cost of each shortcut to the improvement in length to reach the final vertex z of the separator. However, the definition of L_i uses d_T(r, a_i) + l(P_i) + l(Q[v_i, z]), where d_T(r, a_i) is the distance in the current solution T before buying P_i.

more of objection 3

The inequality c(P_i)/(X_H log k) ≤ (L_{i-1} - L_i)/(ε h) relies on the assumption that the existing path to v_i before buying P_i is exactly the path through the previous shortcut and the separator subpath. But the solution T may contain multiple paths to v_i; the distance d_T(r, v_i) is the minimum over all paths, not necessarily the one through the previous shortcut. If there is a shorter path to v_i that does not go through the previous shortcut, then the inequality may not hold because the improvement Δ_i could be smaller than claimed. The authors should argue that the path through the previous shortcut is indeed the shortest path to v_i in T before buying P_i, or provide a more careful charging argument that does not rely on this assumption.

The paper says, at §4.1, Step 2: Constructing Candidate Rooted Solutions

The review did not quote this passage.

Pith says: Objection 4 of 4 · major

The construction of candidate solutions uses the median distance a_i from s_i to chunk C along paths in P_hi ∩ P_C, weighted by f_p. The median is defined such that at least half the flow from s_i to C has length ≤ a_i, and at least half the flow from C to t_i has length ≤ h - a_i.

more of objection 4

However, the flow paths in P_hi ∩ P_C are s_i-t_i paths, not s_i-C or C-t_i paths. The subpaths from s_i to C and from C to t_i are not necessarily independent; the flow on a path p is counted in both the s_i-C and C-t_i parts. The median condition ensures that there is a set of paths with total flow at least β/2 from s_i to C of length ≤ a_i, and similarly from C to t_i of length ≤ h - a_i, but these sets may be different. The LC-ST algorithm then connects s_i' and t_i' to the root r_C, but the paths from s_i' to r_C and from r_C to t_i' may use different flow paths, and the concatenation may not correspond to a single s_i-t_i path of length ≤ h. The authors should clarify how the median trick guarantees a feasible s_i-t_i path of length ≤ (1+ε)h, given that the two halves may come from different flow paths.

7 minor objections

The paper says, at Abstract

Pith says: minor objection 1 of 7

The abstract states 'We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs.' This is accurate for the directed and multicommodity problems, but for LC-ST on planar graphs, Hershkowitz and Huang [33] already gave an O(log^{1+ε} k) approximation with 1+ε length slack. The authors should clarify that 'these problems' refers to the directed and multicommodity variants, or adjust the wording to avoid overclaiming.

The paper says, at §1.1, Table 1

Pith says: minor objection 2 of 7

The table lists the LC-DST result from [12] as having cost O(log^2 k) and length slack O(log k), but the text in §1.1 says 'O(log^2 k) LP-competitive approximation with length slack O(log k) for LC-DST'. The table should include a note that the [12] result is LP-competitive, or the text should be consistent.

more of objection 2

Currently the table says 'No' for LP-competitive for the first [12] row, but the second [12] row says 'Yes'. This is confusing; the authors should clarify which result is which.

show 5 more

The paper says, at §3.1, Definition 3.2

Pith says: minor objection 3 of 7

The hierarchical mixture metric w_H(e) = l(e)/(ε h) + c(e)/(X_H log k) uses X_H, which is defined as the sum of c(e) x_e over edges in region H. However, after buying separator edges, their costs are set to 0 for the remainder of the algorithm, but X_H remains its original value. This is stated in the text, but it would be helpful to explicitly note that X_H is not updated after separator edges are bought, to avoid confusion.

The paper says, at §4.1, Algorithm 5

Pith says: minor objection 4 of 7

In Algorithm 5, the recursion on connected components of G \(Q_1 ∪ Q_2 ∪ Q_3) is described, but it is not specified how the root r is chosen for each recursive call. The separator lemma (Lemma 2.3) requires a root, but the algorithm says 'from an arbitrary root r ∈ V'.

more of objection 4

If the root is chosen arbitrarily, the separator paths may not be balanced with respect to the terminal pairs in that component. The authors should specify how the root is chosen in each recursive call, or argue that any root works.

The paper says, at §5, Theorem 1.4

Pith says: minor objection 5 of 7

The hardness result for LC-SF states that there is no polynomial time 2^{log^{1-ε} k} approximation with length slack β < 3. However, the reduction uses a constant δ that depends on β, and the length constraint h = 1 + 4δ. The hardness is for general graphs, not planar graphs. The authors should explicitly state that the hardness is for general graphs, as the rest of the paper focuses on planar graphs.

The paper says, at §6, Acknowledgements

Pith says: minor objection 6 of 7

The AI disclosure is unusual but appreciated. However, the authors state that GPT-6 Astra improved the LC-DST bound from O(log^4 k/ε^3) to O(log^2 k/ε) and provided the path preprocessing and flow threshold arguments for LC-SF. This raises questions about the novelty and attribution of the key ideas. The authors should ensure that the contributions of the AI are clearly delineated and that the authors take full responsibility for correctness, as they do.

The paper says, at General

Pith says: minor objection 7 of 7

The paper uses the term 'LP-competitive' to mean that the cost of the solution is bounded by a polylogarithmic factor times the LP optimum. This is standard, but the authors should define it explicitly in the preliminaries, as it is used throughout.

What would settle it

Recompute Lemma 4.3 and Lemma 4.7 after the 4/3 scaling: define X' = (4/3)X, γ'_j = (X'/k) τ^j, and verify that for every path p in the scaled bucket Bj, w'_j(p) ≤ 2γ'_j still holds. If the inequality fails, recompute the chunk-per-vertex bound in Lemma 4.7 and the total weighted cost in Lemma 4.11; if the exponent of log k increases, the O(log^5 k/ϵ^2) claim may be invalid.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic partly agrees 14 s · 34,194 tokens read, 1,126 written
  3. Editor wrote the verdict above 33 s · 35,988 tokens read, 621 written
  4. Referee major revision: 4 major objections, 7 minor 17 s · 34,595 tokens read, 2,430 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

This is a serious theory paper and on my reading the main results are real. The headline is LC-DST at O(log2 k/epsilon) with 1+epsilon slack, LP-competitive: it improves Hershkowitz-Huang's O(log3 k/epsilon) undirected LC-ST result and moves to the directed setting, and it tightens Chekuri-Jain's O(log k) slack down to 1+epsilon. The cost-to-length / length-to-cost charging is the genuinely new idea, and I traced it end to end. Lemma 3.8's separator bounds follow from the pruning radius; Lemma 3.9's shortcut cost telescopes against cumulative length improvement toward the separator endpoint with L1 - Lm <= O(h); the canonical-path argument closes the length budget at h + epsilon h. I found no error in that pipeline.

LC-SF is where the work is, and it is dense. The stress-test note flags a scaling inconsistency: after Lemma 4.2 discards paths of cost >= 4X and rescales the flow by 4/3, are the bucket boundaries gamma_j = (X/k) tauj stale? I went back to the text and I think that concern does not land. Bucketing is by actual path cost, which is invariant to flow scaling; Lemma 4.3's bound wj(p) <= 2 gamma_j uses c(p) <= gamma_j and l(p) <= h, both unchanged. The 4/3 enters only the final constant, and the paper says exactly that at the end of Section 4.2. I would not hold that against the authors.

What I would want a referee to sit with: the per-vertex chunk-membership bound in Lemma 4.7, the covering argument in Lemma 4.8, and the weighted averaging hinge (Lemma 4.6 into Lemma 4.11). Those constants are load-bearing and not all fully instantiated. I could not re-derive every inequality in Section 4.2 in one sitting; nothing contradicted itself, but it deserves a careful reader. The LC-DSF result rests on Lemma A.1 quoted from Chekuri-Jain [12], which is published, so that is supported rather than a soft spot. The AI disclosure is honest and argues for a watchful referee, not distrust.

Verdict: send to review. I would want Section 4 checked before signing off, but the LC-DST result alone is a solid contribution worth the reading group.

The strongest objection

The LC-SF cost analysis (Section 4.2) depends on a chain of inequalities whose constants are not fully instantiated. The critical step is Lemma 4.7, which bounds the number of chunks containing a given vertex by O(log^2 k/(ϵ log τ)). This bound multiplies three sources: (i) O(1/ϵ) chunks per separator path (derived from the mixture-cost bound of 4γ_j on the subpath between the first and last intersection points), (ii) O(log k) levels of recursion, and (iii) O(log k / log τ) buckets. The derivation of (i) uses Lemma 4.3, which states that every path in bucket Bj has mixture cost at most 2γ_j. However, Lemma 4.3 relies on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions (γ_j = (X/k) τ^j) are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in Bj, potentially increasing the number of chunks per vertex beyond O(1/ϵ). The subsequent weighted averaging (Lemma 4.6) and the bound on total weighted cost (Lemma 4.11) depend on the chunk-membership bound of Lemma 4.7; if that bound is off by a factor, the final O(log^5 k/ϵ^2) approximation ratio could be understated. The authors acknowledge the preprocessing step (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This is a concrete gap that could affect the correctness of the LC-SF cost guarantee.

The reader identified the LC-SF small-intersection property and the bucketing as the weakest assumption, which aligns with my concern. However, the reader did not flag the specific interaction between the 4/3 scaling and the mixture-cost bound in Lemma 4.3, which is the precise technical gap I see. The reader's verdict is CONDITIONAL, which I agree with; I do not see a reason to change it to REJECT because the gap may be fixable by adjusting constants or by redefining γ_j after scaling. The paper's own disclosure of AI assistance and the acknowledged complexity of the LC-SF proof further support a CONDITIONAL verdict. I therefore recommend UNCHANGED (i.e., the reader's CONDITIONAL stands). The agreement_with_reader is 'partial' because the reader's weakest_assumption is about the small-intersection property, which is related but not identical to the scaling-mixture interaction I highlight.

The referee's report

If correct, these results resolve open questions about the existence of O(1)-slack polylogarithmic approximations for directed and multicommodity length-constrained problems on planar graphs. The LP-competitive bounds for LC-DST and LC-SF also give the first upper bounds on the integrality gaps of natural LP relaxations for these problems on planar graphs. The techniques, particularly the cost-to-length and length-to-cost charging framework, are novel and may be of independent interest. The hardness results separate planar from general graphs, which is a clean contribution.

Pith's reading of the paper (a machine's summary, not the authors')

Network design problems ask how to build a cheap network that connects specified points. The length-constrained versions add the requirement that each connection is made by a path that is short, not just cheap. On general graphs these problems are very hard, and prior good approximations were allowed to stretch the path-length limit by a logarithmic factor. This paper works on planar graphs, meaning graphs that can be drawn on a flat surface without edges crossing, and shows that for the directed and multi-pair versions the stretch can be reduced to a constant, and even to 1+epsilon for the single-customer directed version.

The core technical trick is a charging argument. When the algorithm buys a shortcut path, it argues that the cost of that shortcut is paid for by the improvement it creates in the total path length to the far end of the separator. Conversely, when the resulting root-terminal paths are too long, each extra unit of length is charged to the cost of a comparison path lying inside the same region. Since the comparison paths are bounded by the linear programming relaxation of the problem, the charges stay small and the length budget closes at (1+epsilon) times the allowed length. The multi-pair version routes demands through junction points, using a median-distance trick so each endpoint keeps half of its flow under a separate length budget.

The paper also proves these problems are genuinely easier on planar graphs. By reducing from the Min-Rep problem, it shows that on general graphs no polylogarithmic approximation is possible with length slack below 3 for Steiner forest, and no length slack at all for its directed version, assuming standard complexity conjectures.

Core claim. Theorem 1.1: for any epsilon in (0,1), there is an LP-competitive O(log^2 k / epsilon) approximation with 1+epsilon length slack for LC-DST in planar graphs, running in poly(n,1/epsilon). Companion Theorems 1.2 and 1.3 give an LP-competitive O(log^5 k / epsilon^2) approximation with 1+epsilon slack for LC-SF and an O(log^6 k / epsilon) approximation with 6+epsilon slack for LC-DSF. If correct, these are the first O(1)-slack polylogarithmic approximations for the directed and multicommodity length-constrained problems on planar graphs, resolving the open questions posed in the introduction.

The premise it rests on. The LC-SF construction rests on the claim (end of Section 1.2.2) that for any separator path Q and terminal pair (s_i,t_i), the LP's s_i-t_i flow intersects Q only on a small subpath, with the paper's own acknowledged caveat that this holds only when all flow paths have roughly the same cost, handled by bucketing paths into (X/k, 4X) cost buckets. This small-intersection property drives the chunk charging (Lemma 4.7's O(log^2 k/(epsilon log tau)) per-vertex chunk-membership bound) and the flow-threshold covering Lemma 4.8; if flow paths spanned long separator subpaths, the chunk count and hence the log^5 k bound would inflate. The fragile step is the fixed-proportion preprocessing (dropping paths of cost at least 4X and scaling the remainder by 4/3, Lemma 4.2), which must preserve at least 3/4 unit of flow per demand.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

Problems in length-constrained network design ask for min-cost subgraphs connecting k input vertex pairs by paths of length at most h. Algorithms that instead connect these pairs by paths of length at most βh are said to have length slack β. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack 1 + ε and approximation ratios of O(log2k/ε) for directed Steiner tree and O(log5k/ε2) for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an O(log6k/ε) approximation on planar graphs with length slack 6 + ε. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below 3.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-14

The authors' main claim, as the classifier picked it out 1.00

“We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.93 · states limitation 0.46 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.95 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. background 1.00 0.05 0.02 asserted 0.99
Algorithms that instead connect these pairs by paths of length at most $\beta h$ are said to have length slack $\beta$. background 1.00 0.07 0.03 asserted 0.98
Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. background 0.97 0.04 0.05 asserted 0.75
We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. contribution 0.95 0.97 0.85 asserted 1.00
In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+\epsilon$ and approximation ratios of $O(\log^2 k/\epsilon)$ for directed Steiner tree and $O(\log^5 k/\epsilon^2)$ for (undirected) Steiner forest. result 0.73 0.97 0.31 asserted 1.00
Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/\epsilon)$ approximation on planar graphs with length slack $6+\epsilon$. result 0.79 0.97 0.11 asserted 1.00
Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. method 1.00 0.94 0.04 asserted 1.00
We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$. result 0.67 0.92 0.12 asserted 0.96

What kind of paper the classifier reports this is: method or tool 0.51 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 6,506 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (10)
Figure 1 of the paper
Figure 1. Shortest-path separators (red) in initial graph and in resulting components
Figure 2 of the paper
Figure 2. The shortcuts to pieces in the algorithm of Hershkowitz and Huang [33] for LC-ST and how it fails to generalize to LC-DST. Figure 2a: a horizontal parent and child separator path, and two pieces on the child separator whose shortcuts enter on vertices a, b. Figure 2b: if the separators are directed paths, then a cannot reach vertices in its piece that lie before it on the path like c, but b can still reach d. Our Approach. Our algorithm bypasses the need for fixed O(log k) pieces and cost bounds on shortcuts, by instead greedily choosing shortcuts according to a hierarchical mixture…
Figure 3 of the paper
Figure 3. The way we buy shortcuts. Figure 3a: horizontal parent and child separators, and a previously bought shortcut to a. The candidate shortcut from the parent separator to b is in dotted black. Figures 3b and 3c: two possible paths to reach b, one using the previously bought shortcut to a and the subpath on the child separator from a to b, and one using the candidate shortcut from the parent to b; we buy the candidate shortcut to b if it is faster (under the lengths) for the solution to reach b when taking the shortcut versus using the previous shortcut to a and then the a-b subpath on…
Figure 4 of the paper
Figure 4. Three junction trees rooted at v1, v2, v3 covering terminal pairs. 1.2.2 Length-Constrained Steiner Forest We build on the well-known junction tree technique via new analysis that allows for 1 + ϵ length slack, and, more importantly, is LP-competitive. Junction Trees. The junction tree technique was used by several earlier works in LC-SF (e.g. [14; 12]). It reduces a multicommodity problem to its single-source counterpart. A junction tree is a partial solution (i.e. a subgraph that is feasible for a subset of terminal pairs) that connects pairs through a junction vertex, see
Figure 5 of the paper
Figure 5. Example of flow paths intersecting separator
Figure 6 of the paper
Figure 6. Charging shortcut cost to improvements in length. In the region
Figure 7 of the paper
Figure 7. Charging length to canonical path cost. Pictured is a canonical
Figure 8 of the paper
Figure 8. Constructing an LC-ST instance for chunk
Figure 9 of the paper
Figure 9. Red paths denote all p ∈ ∪C∈CQ PC containing v. The mixture cost of each of these paths is at most 2γj , giving us a bound on the mixture cost of Q[u1, u2]. Proof. Fix a vertex v ∈ V , a bucket Bj and a separator path Q. Let CQ denote the set of all chunks of Q. Consider the set of all points u ∈ V (Q) such that there exists a path p ∈ ∪C∈CQ PC with u, v ∈ V (p). Let u1, u2 ∈ V (Q) be the closest and furthest such points from r. This implies that v ∈ V (PC ) only for chunks with non-empty intersection with Q[u1, u2]. Recall, by Lemma 4.3, that all paths in Bj (and thus all paths in…
Figure 10 of the paper
Figure 10. The reduction from Min-Rep to LC-SF. Figure 10a: a Min-Rep instance on graph G = (A ∪ B = {u1, u2} ∪ {v1, v2}, E = {e1, e2, e3}), with some unpictured set of labels and valid label pairs. Figure 10b: the corresponding LC-SF instance H where V (H)1 is blue, V (H)2, V (H)3 are green, V (H)4, V (H)5 are red, and V (H)6 is yellow. Note the reduction to LC-DSF is identical but with edges directed from left to right. Figure 10c: an LC-SF solution in H corresponding to a Min-Rep solution in G. 6 Acknowledgements AI Disclosure. The authors initially discovered a poly-time LP-competitive O…

Figures are the authors', reproduced from the paper.

References (46)
  1. [12] Chandra Chekuri and Rhea Jain. Length-Constrained Network Design in Planar Digraphs. InAp- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX- /RANDOM), volume 392, pages 15:1–15:24, 2026 on Pith
  2. [1] Ajit Agrawal, Philip Klein, and Ramamoorthi Ravi. When trees collide: An approximation algorithm for the generalized steiner problem on networks. InAnnual ACM Symposium on Theory of Computing (STOC), pages 134–144, 1991 on Pith
  3. [2] Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mah- 29 davi. Breaking a long-standing barrier: 2-εapproximation for steiner forest. InSymposium on Founda- tions of Computer Science (FOCS), pages 373–444, 2025 on Pith
  4. [3] Ibrahim Akg¨ un and Barbaros C ¸ 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 on Pith
  5. [4] Baruch Awerbuch and Yossi Azar. Buy-at-bulk network design. InSymposium on Foundations of Computer Science (FOCS), pages 542–547, 1997 on Pith
  6. [5] Amy Babay, Michael Dinitz, and Zeyu Zhang. Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. InIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 122, pages 33:1–33:22, 2018 on Pith
  7. [6] 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 on Pithdoi:10.1287/ijoc.4
  8. [7] Jaros law Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanit` a. Steiner tree approximation via iterative randomized rounding.Journal of the ACM (JACM), 60(1):1–33, 2013 on Pith
  9. [8] Moses Charikar and Adriana Karagiozova. On non-uniform multicommodity buy-at-bulk network design. InProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 176–182, New York, NY, USA, 2005. Association for Computing Machinery. doi: 10.114... on Pithdoi:10.1145/1060590.1060617
  10. [9] 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 on Pith
  11. [10] Chandra Chekuri and Rhea Jain. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing. InAnnual European Symposium on Algorithms (ESA), volume 308, pages 41:1–41:21, 2024 on Pith
  12. [11] Chandra Chekuri and Rhea Jain. A polylogarithmic approximation for directed steiner forest in planar digraphs. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2095–2110, 2025 on Pith
  13. [13] Chandra Chekuri, Sanjeev Khanna, and Joseph (Seffi) Naor. A deterministic algorithm for the cost- distance problem. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 232–233, 2001 on Pith
  14. [14] Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour. Ap- proximation algorithms for nonuniform buy-at-bulk network design.SIAM Journal on Computing, 39 (5):1772–1798, 2010 on Pith
  15. [15] Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. InAnnual European Symposium on Algorithms (ESA), volume 308, pages 42:1–42:19, 2024 on Pith
  16. [16] Erik D Demaine, MohammadTaghi Hajiaghayi, and Philip N Klein. Node-weighted steiner tree and group steiner tree in planar graphs. InInternational Colloquium on Automata, Languages and Pro- gramming (ICALP), pages 328–340, 2009 on Pith
  17. [17] Michael Dinitz, Guy Kortsarz, and Ran Raz. Label cover instances with large girth and the hardness of approximating basic k-spanner.ACM Transactions on Algorithms (TALG), 12(2):1–16, 2015. 30 on Pith
  18. [18] Arnold Filtser. Hop-constrained metric embeddings and their applications. InSymposium on Founda- tions of Computer Science (FOCS), pages 492–503, 2022 on Pith
  19. [19] Willem Fletcher and D Ellis Hershkowitz. Spanning tree embeddings are not much harder than hierar- chical partitions. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5344–5373, 2026 on Pith
  20. [20] Zachary Friggstad and Ramin Mousavi. An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. InInternational Colloquium on Automata, Languages and Programming (ICALP), volume 261, pages 63:1–63:14, 2023 on Pith
show 26 more
  1. [21] Zachary Friggstad and Ramin Mousavi. A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. InApproximation, Randomization, and Combinatorial Optimiza- tion. Algorithms and Techniques (APPROX/RANDOM), volume 275, pages 13:1–13:18, 2023 on Pith
  2. [22] Michael R Garey and David S Johnson.Computers and intractability, volume 29. W. H. Freeman, 2002 on Pith
  3. [23] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. InPro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1208–1220, 2021 on Pith
  4. [24] 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 on Pith
  5. [25] Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O (log2 k/log log k)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm. InAnnual ACM Symposium on Theory of Computing (STOC), pages 253–264, 2019 on Pith
  6. [26] Anupam Gupta and Amit Kumar. Greedy algorithms for steiner forest. InAnnual ACM Symposium on Theory of Computing (STOC), pages 871–878, 2015 on Pith
  7. [27] Anupam Gupta and Vera Traub. Steiner forest: A simplified better-than-2 approximation. InAnnual ACM Symposium on Theory of Computing (STOC), pages 943–954, 2026 on Pith
  8. [28] Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic. Tree embeddings for hop-constrained net- work design. InAnnual ACM Symposium on Theory of Computing (STOC), pages 356–369, 2021 on Pith
  9. [29] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. New structures and algorithms for length- constrained expander decompositions. InSymposium on Foundations of Computer Science (FOCS), pages 1634–1645, 2024 on Pith
  10. [30] Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. InAnnual ACM Sympo- sium on Theory of Computing (STOC), pages 585–594, 2003 on Pith
  11. [31] Refael Hassin. Approximation schemes for the restricted shortest path problem.Mathematics of Oper- ations research, 17(1):36–42, 1992 on Pith
  12. [32] D Ellis Hershkowitz and Richard Z Huang. Simple length-constrained minimum spanning trees. In Symposium on Simplicity in Algorithms (SOSA), pages 341–349, 2025 on Pith
  13. [33] D Ellis Hershkowitz and Richard Z Huang. Planar length-constrained minimum spanning trees. In Annual ACM Symposium on Theory of Computing (STOC), pages 1528–1539, 2026 on Pith
  14. [34] Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Plane gossip: Approximating rumor spread in planar graphs. InLatin American Symposium on Theoretical Informatics (LATIN), pages 611–624, 2018 on Pith
  15. [35] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of planar quasimetrics into directed ℓ1 and polylogarithmic approximation for directed sparsest-cut. InSymposium on Foundations of Com- puter Science (FOCS), pages 480–491, 2021. 31 on Pith
  16. [36] M Reza Khani and Mohammad R Salavatipour. Improved approximations for buy-at-bulk and shallow- light k-steiner trees and (k, 2)-subgraph.Journal of Combinatorial Optimization, 31(2):669–685, 2016 on Pith
  17. [37] Lawrence Kou, George Markowsky, and Leonard Berman. A fast algorithm for steiner trees.Acta Informatica, 15(2):141–145, 1981 on Pith
  18. [38] Shi Li and Bundit Laekhanukit. Polynomial integrality gap of flow lp for directed steiner tree. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3230–3236, 2022 on Pith
  19. [39] Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979 on Pith
  20. [40] Madhav V Marathe, Ramamoorthi Ravi, Ravi Sundaram, SS Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Bicriteria network design problems.Journal of Algorithms, 28(1):142–171, 1998 on Pith
  21. [41] Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Cost-distance: Two metric network design. In Symposium on Foundations of Computer Science (FOCS), pages 624–630, 2000 on Pith
  22. [42] F Sibel Salman, Joseph Cheriyan, Ramamoorthi Ravi, and Sairam Subramanian. Approximating the single-sink link-installation problem in network design.SIAM Journal on Optimization, 11(3):595–610, on Pith
  23. [43] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs.Journal of the ACM (JACM), 51(6):993–1024, 2004 on Pith
  24. [44] Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica, 18(1):99–110, 1997 on Pith
  25. [45] Leonid Zosin and Samir Khuller. On directed Steiner trees. InProceedings of ACM-SIAM SODA, pages 59–63, 2002. A Length-Constrained Directed Steiner Forest We use the modularity of the planar LC-DSF algorithm of Chekuri and Jain [12]. Lemma A.1(Theorem 4.1, Lemma 4.12, and Theo... on Pith
  26. [2001] Preliminary version in Proc. of SODA 1997 on Pith

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment