pith. sign in

arxiv: 1907.03474 · v1 · pith:BTOUSOS5new · submitted 2019-07-08 · 🧮 math.CO · cs.DM

The 2-connected bottleneck Steiner network problem is NP-hard in any ell_p plane

M Brazil , C Ras , D Thomas , G Xu This is my paper

Pith reviewed 2026-05-25 01:24 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords bottleneck Steiner network2-connectedNP-hardnessℓ_p normsapproximation hardnessSteiner pointswireless networks
0
0 comments X

The pith

The 2-connected bottleneck Steiner network problem is NP-hard in any ℓ_p plane.

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

The paper establishes that constructing a minimum-bottleneck 2-connected network spanning given terminals, using at most k Steiner points, is NP-hard when edge lengths are measured under any ℓ_p norm in the plane. This extends prior work on the tree case in the Euclidean plane to fault-tolerant networks. The result matters because these networks model energy consumption in wireless ad-hoc systems where the longest edge determines power use. If correct, neither exact solutions nor approximations better than a specific factor can be found in polynomial time unless P equals NP. The hardness holds for every finite p at least 1.

Core claim

We show that the 2-connected bottleneck Steiner network problem is NP-hard in any planar p-norm and, in fact, if P≠NP then an optimal solution cannot be approximated to within a ratio of 2^{1/p}−ε in polynomial time for any ε>0 and 1≤p<∞.

What carries the argument

A polynomial-time reduction from a known NP-hard problem to the 2-connected bottleneck Steiner network problem in the ℓ_p plane that preserves the bottleneck length and connectivity properties.

If this is right

  • No polynomial-time exact algorithm exists for the problem unless P=NP.
  • No polynomial-time approximation algorithm achieves a ratio better than 2^{1/p}−ε for any ε>0.
  • The hardness result applies to every p-norm with 1≤p<∞.

Where Pith is reading between the lines

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

  • The same style of reduction may extend to k-connected versions for k greater than 2.
  • Heuristic or exponential-time methods will remain necessary for exact solutions in non-Euclidean metrics.
  • The p-dependent inapproximability threshold suggests that algorithmic performance could differ noticeably between L1 and Euclidean cases.

Load-bearing premise

A polynomial-time reduction exists from a known NP-hard problem to an instance of the 2-connected bottleneck Steiner network problem in the ℓ_p plane that preserves the bottleneck length and connectivity properties.

What would settle it

A polynomial-time algorithm that solves the problem exactly or approximates it within a ratio smaller than 2^{1/p}−ε for some fixed p and ε>0 would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.03474 by C Ras, D Thomas, G Xu, M Brazil.

Figure 1
Figure 1. Figure 1: Illustration for the proof of Lemma 4 The following lemma will be used in our main proof: Lemma 4. Let v, v1, v2 be three points in the plane such that v1v is parallel to the y-axis, v2v is parallel to the x-axis, kv − v1kp ≥ 2 and kv − v2kp ≥ 2. Let T be a full Steiner tree of minimum bottleneck length on v, v1, v2 such that T contains a single Steiner point. Then the length of the bottleneck edge in T is… view at source ↗
Figure 2
Figure 2. Figure 2: R(ui), represented by dashed lines, for the edge set E(ui). The black-filled circles are terminals of N and are called tips of R(ui). The terminal set X is constructed as follows. For each w ∈ W, let pw be the corresponding grid point in the embedding, and call pw a W-terminal. For each ui ∈ U, let wj , wh and wl be the three neighbours of ui . Note that there is a grid path in G connecting ui and each of … view at source ↗
Figure 3
Figure 3. Figure 3: Many terminals are placed on R(ui). Consecutive pairs of coincident terminals are at a distance of 1 from each other. Large black-filled circles represent pairs of coincident terminals. Next, place two terminals on R(ui) at a distance of exactly 1 from each x s i , s ∈ {j, h, l} (note that the locations of these two terminals coincide). Also, place many pairs of coincident terminals on R(ui) so that the di… view at source ↗
Figure 4
Figure 4. Figure 4: Steiner points (white circles) placed between tip-terminals [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 1
Figure 1. Figure 1: The inapproximability ratio follows from the fact that the smallest [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
read the original abstract

Bottleneck Steiner networks model energy consumption in wireless ad-hoc networks. The task is to design a network spanning a given set of terminals and at most $k$ Steiner points such that the length of the longest edge is minimised. The problem has been extensively studied for the case where an optimal solution is a tree in the Euclidean plane. However, in order to model a wider range of applications, including fault-tolerant networks, it is necessary to consider multi-connectivity constraints for networks embedded in more general metrics. We show that the $2$-connected bottleneck Steiner network problem is NP-hard in any planar $p$-norm and, in fact, if P$\,\neq\,$NP then an optimal solution cannot be approximated to within a ratio of ${2}^\frac{1}{p}-\epsilon$ in polynomial time for any $\epsilon >0$ and $1\leq p< \infty$.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 0 minor

Summary. The paper claims to establish that the 2-connected bottleneck Steiner network problem (minimizing the longest edge in a 2-connected network spanning terminals with at most k Steiner points) is NP-hard in the plane under any ℓ_p norm for 1 ≤ p < ∞. It further claims an inapproximability threshold of 2^{1/p} − ε (for any ε > 0) unless P = NP.

Significance. If the central reduction is valid, the result extends known Euclidean hardness to the full family of ℓ_p norms with a p-dependent inapproximability bound. This would be useful for fault-tolerant wireless network design, as it rules out constant-factor approximations that are independent of p. The uniform treatment across all finite p is a potential strength if the construction controls distance scaling correctly.

major comments (2)
  1. [Reduction (implicit in abstract and claimed proof)] The NP-hardness and inapproximability rest on a single polynomial-time reduction that must simultaneously preserve exact bottleneck length and enforce 2-connectivity while remaining valid for every 1 ≤ p < ∞. Because the shape of the ℓ_p unit ball, the constants in the triangle inequality, and the possibility of collinear shortcuts all vary with p, the construction must explicitly rule out p-dependent shortcuts or connectivity violations (e.g., for p = 1 or as p → ∞). No such verification is visible in the provided text.
  2. [Proof of Theorem (not visible)] The source problem of the reduction is not identified, nor is any gadget description or distance-preservation argument supplied. Without these, it is impossible to check whether the reduction remains polynomial-time and exact for the bottleneck objective across the entire range of p.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater clarity in the presentation of the reduction. The comments correctly note that the current text does not make the p-uniform verification explicit. We will revise the manuscript to supply the missing details.

read point-by-point responses

  1. Referee: [Reduction (implicit in abstract and claimed proof)] The NP-hardness and inapproximability rest on a single polynomial-time reduction that must simultaneously preserve exact bottleneck length and enforce 2-connectivity while remaining valid for every 1 ≤ p < ∞. Because the shape of the ℓ_p unit ball, the constants in the triangle inequality, and the possibility of collinear shortcuts all vary with p, the construction must explicitly rule out p-dependent shortcuts or connectivity violations (e.g., for p = 1 or as p → ∞). No such verification is visible in the provided text.

    Authors: We agree that an explicit, p-by-p verification is required and is not sufficiently visible in the current version. In the revision we will insert a dedicated subsection (or appendix) that (i) states the precise positions of all terminals and Steiner points in the gadgets, (ii) proves that no ℓ_p-shortcut of strictly smaller bottleneck length exists for any 1 ≤ p < ∞, and (iii) verifies 2-connectivity is preserved even when the unit ball degenerates at p = 1 and p → ∞. The argument will rely on the fact that all critical distances are realized by axis-aligned or 45-degree segments whose ℓ_p lengths scale identically. revision: yes

  2. Referee: [Proof of Theorem (not visible)] The source problem of the reduction is not identified, nor is any gadget description or distance-preservation argument supplied. Without these, it is impossible to check whether the reduction remains polynomial-time and exact for the bottleneck objective across the entire range of p.

    Authors: We will expand the proof of the main theorem to (a) name the source NP-complete problem, (b) give a complete description of every gadget together with its terminal/Steiner-point coordinates, and (c) supply a self-contained lemma establishing that the constructed instance has bottleneck length exactly equal to the source instance if and only if the source instance is yes, with the equality holding uniformly for every p. The polynomial-time claim will be restated with an explicit bound on the number of points created. revision: yes

Circularity Check

0 steps flagged

Standard NP-hardness proof; no circularity

full rationale

The paper establishes NP-hardness and inapproximability of the 2-connected bottleneck Steiner network problem in ℓ_p planes by means of a polynomial-time reduction from an external known NP-hard problem. No equations, fitted parameters, self-definitions, or load-bearing self-citations appear in the derivation. The reduction is a direct combinatorial construction that preserves bottleneck lengths and 2-connectivity; it does not reduce to any input of the present paper by construction. This is the normal, non-circular case for a hardness proof.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is a complexity-theoretic statement whose proof (not visible) would rest on standard reduction techniques from known NP-hard geometric problems; no free parameters, invented entities, or non-standard axioms are indicated in the abstract.

axioms (1)
  • standard math Polynomial-time reductions from known NP-hard problems can be constructed that preserve bottleneck lengths and 2-connectivity in ℓ_p metrics.
    Typical mechanism for proving geometric NP-hardness results.

pith-pipeline@v0.9.0 · 5689 in / 1192 out tokens · 33568 ms · 2026-05-25T01:24:53.812359+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

15 extracted references

  1. [1]

    Abu-Affash, P

    A.K. Abu-Affash, P. Carmi, M.J. Katz and M. Segal, The Euclidean bottleneck Steiner path problem and other applications of (α,β )-pair de- composition, Discrete and Computational Geometry 51(1), 2014, 1–23. 10

    2014

  2. [2]

    Akiyama, T

    T. Akiyama, T. Nishizeki and N. Saito, NP-completeness of the Hamilto- nian cycle problem for bipartite graphs,Journal of Information processing 3, 1980, 73–76

    1980

  3. [3]

    Arampatzis, L

    T. Arampatzis, L. Lygeros and J.S. Manesis, A survey of applications of wireless sensors and wireless sensor networks, Proc. 13th Mediterranean Conf. on Control and Automation (2005), 719–724

    2005

  4. [4]

    S.W. Bae, S. Choi, C. Lee and S. Tanigawa, Exact algorithms for the bottleneck Steiner tree problem, Algorithmica 61, 2011, 924–948

    2011

  5. [5]

    Brazil, C.J

    M. Brazil, C.J. Ras and D.A. Thomas, The bottleneck 2-connected k- Steiner network problem for k≤ 2, Discrete Applied Mathematics , 160, 2012, 1028–1038

    2012

  6. [6]

    Brazil, C.J

    M. Brazil, C.J. Ras and D.A. Thomas, An exact algorithm for the bottle- neck 2-connectedk-Steiner problem in Lp planes, Discrete Applied Math- ematics, 201, 2016, 47–69

    2016

  7. [7]

    Chang, C.Y Tang and R.C Lee, Solving the Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs, Discrete Applied Mathematics , 39(1) ,1992, 1–12

    M.S. Chang, C.Y Tang and R.C Lee, Solving the Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs, Discrete Applied Mathematics , 39(1) ,1992, 1–12

    1992

  8. [8]

    Czumaj and A

    A. Czumaj and A. Lingas, On approximability of the minimum-cost k- connected spanning subgraph problem, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms , (1999), 281-290

    1999

  9. [9]

    Z-M. Li, D-M. Zhu and S-H. Ma, Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane,Journal of Computer Science and Technology 19(6), 2004, 791–794

    2004

  10. [10]

    Luebke and J.S

    E.L. Luebke and J.S. Provan, On the structure and complexity of the 2-connected Steiner network problem in the plane, Operations Research Letters, 26, 2000, 111–116. 11

    2000

  11. [11]

    Ras, Survivable minimum bottleneck networks, Computational Ge- ometry, 50, 17–23

    C.J. Ras, Survivable minimum bottleneck networks, Computational Ge- ometry, 50, 17–23

  12. [12]

    Simon, M

    G. Simon, M. Maroti, A. Ledeczi, G. Balogh, B. Kusy, A. Nadas, G. Pap, J. Sallai and K. Frampton, Sensor network-based countersniper system, Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (2004), 1–12

    2004

  13. [13]

    Tamassia and I

    R. Tamassia and I. G. Tollis, Planar grid embedding in linear time, IEEE Transactions on Circuits and Systems 36, 1989, 1230–1234

    1989

  14. [14]

    T. Wark, P. Corke, P. Sikka, L. Klingbeil, Y. Guo, C. Crossman, P. Va- lencia, D. Swain and G. Bishop-Hurley, Transforming agriculture through pervasive wireless sensor networks, Pervasive Computing IEEE , 6, 2007, 50–57

    2007

  15. [15]

    Wang and D.Z

    L. Wang and D.Z. Du, Approximations for a bottleneck Steiner tree problem, Algorithmica, 32, 2002, 554–561. 12

    2002