# Verification report — OWR-730-009 (exact complexity of ε-Dense Steiner Tree)

Verification date: 2026-09-29.

**Verdict.** Resolved conditionally, in the only form possible without separating P from NP. For every fixed
ε ∈ (0,1], exact ε-Dense Steiner Tree is solvable in time n^{O(log n/ε)}, so it is not NP-hard (even under
polynomial-time Turing reductions) unless NP ⊆ DTIME(2^{O(log² n)}). For every fixed ε ∈ (0,1) it has no
N^{o(log N)}-time algorithm unless the Exponential Time Hypothesis (ETH) fails, and it is W[2]-hard when
parameterized by the number of Steiner vertices, so it is not in P unless FPT = W[2]. Hence, assuming ETH, the
problem is neither in P nor NP-hard. The hypotheses are kept separate: "not NP-hard" needs only NP ⊄ QP; "not in
P" needs ETH, or alternatively FPT ≠ W[2]. For polynomially small density the picture is different: by an earlier
result of Cardinal, Karpinski, Schmied and Viehmann (CKSV11, Theorem 5.2 of the full version), Steiner Tree is
APX-hard, hence NP-hard, at density ε = |N|^{−δ} for every fixed δ > 0. So the problem is quasi-polynomial for
ε ≥ 1/polylog n, NP-hard for ε = n^{−δ}, and open in between. The note is unrefereed.

## Statement checked
- **Primary source.** Oberwolfach Report 28/2004, *Approximation Algorithms for NP-Hard Problems* (organisers
  R. Kannan, M. Karpinski, H. J. Prömel), doi:10.4171/OWR/2004/28.
  - pp. 1531–1532, M. Hauptmann, *Steiner Tree Problems*. On p. 1532, Problem 3: give hardness results for the
    ε-Dense Steiner Tree Problem. The report adds that it is not even known whether the problem is NP-hard in the
    exact setting.
  - pp. 1492–1495, Hauptmann's abstract *PTAS for Dense Steiner Tree Problems*: the definition. The graph has unit
    edge weights, and every terminal s satisfies |N(s) ∩ (V∖S)| ≥ ε·|V∖S|. The Karpinski–Zelikovsky PTAS is
    stated there. The paper also requires V∖S ≠ ∅; it says that this is its own, harmless, addition.
  - The PDF obtained anonymously through the DOI has the same SHA-1 as the local copy (checked by the audit).
- **Corpus record.** ulamai/UnsolvedMath, OWR-730-009 (status `partially_solved`): "Prove hardness results for
  the ε-dense Steiner Tree problem, including whether exact optimization is NP-hard."

## Readings
| Reading | Answer | Where |
|---|---|---|
| Is exact ε-Dense Steiner Tree NP-hard (Karp reductions)? | No, unless NP ⊆ QP | Thm 1.1, Cor. 3.5 |
| The same under polynomial-time Turing reductions | No, unless NP ⊆ DTIME(2^{O(log² n)}) | Cor. 3.5 |
| Is it polynomial-time solvable? | No, under ETH; and no unless FPT = W[2] | Thm 1.2 |
| "Hardness results" in the sense of lower bounds on running time | no N^{o(log N)} algorithm under ETH; W[2]-hard for the parameter "number of Steiner vertices"; no FPTAS unless in P | Thm 1.2, Cor. 1.3(iii) |
| Approximation hardness (APX-hardness) | not applicable: a PTAS exists [Karpinski–Zelikovsky] | Introduction |
| ε = 1 | trivial (at most one Steiner vertex is needed) | Introduction |
| Density not fixed but polynomially small, ε = \|N\|^{−δ} | NP-hard (indeed APX-hard) by the earlier CKSV11, Thm 5.2; not a result of this paper | §5, "Open questions" |

An unconditional answer to "is it NP-hard?" would decide P vs NP (if P = NP, every nontrivial problem in P is
NP-hard), so a conditional answer is the natural resolution.

## Results in the paper
- **Lemma 3.1 (hubs).** Greedy domination plus pigeonhole merging give H' ⊆ D, where D is the set of
  non-terminals with a terminal neighbour. H' dominates S, |H'| ≤ 2⌊ln k/ε⌋ + 1, and G[S ∪ H'] has at most
  ⌊1/ε⌋ components. This is the only place where density is used.
- **Lemma 3.2 (counting).** Let F be connected on K ⊔ Z with |K| = r, and let every z ∈ Z be a cut vertex. Then
  at most 2r − 2 vertices of Z have a neighbour in K.
  - The proof is a spanning-tree degree count, and the bound is tight.
  - It replaces the weaker 7r − 6 (block–cut tree) of the first version, as the audit suggested.
- **Lemma 3.3 (core lemma; no density needed).** Let H ⊆ D be arbitrary and let r be the number of components of
  G[S ∪ H]. Then every optimal Steiner-vertex set Y* satisfies |Y* ∩ D| ≤ |H| + 2r − 2. Moreover,
  G[S ∪ (Y* ∩ D)] has at most max(1, |Y* ∩ D|) components.
- **Theorem 3.4 = Theorem 1.1.** The algorithm guesses C = Y* ∩ D, with |C| ≤ c := |H'| + 2r − 2, and completes
  it by Dreyfus–Wagner on at most c contracted components.
  - Running time: (n+1)^c 3^c n^{O(1)} with c ≤ 2⌊ln k/ε⌋ + 2⌊1/ε⌋ − 1.
  - The algorithm stays quasi-polynomial for ε ≥ 1/polylog n.
- **Lemmas 4.1–4.4 and Theorem 1.2.** The lower bound is a chain of reductions.
  - The gadget: the sets {x ∈ F_q^d∖{0} : a·x ≠ 0}. Every point lies in a (1 − 1/q) fraction of them, but a cover
    needs exactly d of them.
  - The product lemma: τ = min(τ_1, τ_2).
  - A root vertex joined to all set vertices, which gives an ε-dense instance with opt = min(τ(U,𝓕), d).
  - The Megiddo–Vishkin block encoding of 3-SAT, with k = ⌈√v⌉ blocks.
  - Together these give N = 2^{Θ(√v)} and the ETH bound. The same map is a parameterized reduction from Set
    Cover.
- **Remark 4.5 (revised).** A variant gives the ETH bound for ε-dense Set Cover with distinct sets, for every
  fixed ε ∈ (0,1). The gadget uses one set A_a per one-dimensional subspace of F_q^d (these sets are distinct, each
  point lies in (q^d − q^{d−1})/(q − 1) ≥ ρ|P| of them, and τ = d). Instead of R copies, d ≥ k + 1 is taken least
  with (q^d − 1)/(q − 1) ≥ εm/(ρ − ε), which keeps "τ ≤ k iff τ(U,𝓕) ≤ k" and N = 2^{O(√v)}. The Steiner results
  keep the construction with R copies, where repeated neighbourhoods are harmless. No novelty is claimed for this.
- **§5, "Open questions" (revised).** Credits CKSV11, Thm 5.2 (NP-hardness at density |N|^{−δ}), keeps the
  elementary ε = 1/|N| construction as an illustration, and states the picture above. It adds one observation:
  for ε ≥ n^{−o(1)} the algorithm runs in time 2^{n^{o(1)}}, so NP-hardness there would contradict ETH.

## Computations (scripts and outputs in reproducibility/)
- **Claimant (finder)** (`claimant/`, numpy + scipy/HiGHS, about 1 minute, 0 failures). These scripts were written
  for the first version with the bound 7r − 6. They check:
  - 131 small dense instances, with all 612 optimal Y* found by brute force;
  - 36 larger instances (|N| ≤ 74, opt ≤ 29), solved by an exact MILP;
  - the counting step on 19,035 random graphs;
  - the reduction pieces and the full chain on 16 formulas.

  They were rerun in a scratch copy on 2026-09-29, with identical results apart from timings. The last line of
  `out_small.txt` now states the instance count; this was a cosmetic audit fix.
- **Lead** (`lead/`, standard library only, under one minute, 0 failures).
  - `lead_verify.py`, written from scratch, checks:
    - Lemma 3.2 on all 33,867 labelled graphs with at most 6 vertices, over all 69,757 splits (K arbitrary), and
      on 48,224 random cases with 7–12 vertices, plus the tight example;
    - Lemma 3.3 on 942 random non-dense instances, for all 98,670 admissible H; the bound is attained;
    - Theorem 3.4, with its own Dreyfus–Wagner, against brute force on 100 dense instances;
    - Lemma 4.1 (9 pairs), Lemma 4.3 (35 instances, ε up to 0.75) and the chain (24 formulas).
  - `check_claimant_outputs.py`: all 167 rows recorded by the finder satisfy the sharper bounds 2r − 2 and
    |H'| + 2r − 2.
- **Independent referee** (`referee/`, written during the audit before the paper, standard library only, rerun
  2026-09-29, 0 failures). The referee checked:
  - the counting step on all graphs with at most 6 vertices, and on 60,000 random graphs;
  - Lemma 3.3 in its general form against all admissible H, on 630 + 12,712 random instances and 19,569
    tree-like instances; neither 7r − 6 nor 2r − 2 was ever exceeded;
  - a from-scratch algorithm with brute-force completion, which equals opt;
  - the reduction and the chain, with density and optimum computed directly from the graphs.
- **Second independent referee** (`referee2/referee2_verify.py`, written from the text of the previous version
  before any other script was read, standard library only, about 25 s on 16 cores, 0 failures). It checks:
  - Lemma 3.2 on all labelled graphs with at most 7 vertices (4,033,941 cases, K arbitrary; the maximum of
    |B| − (2r − 2) is exactly 0) and the tight path for r ≤ 8;
  - Lemma 3.3 on all labelled graphs with at most 6 vertices, every terminal set, every optimal Y* and every
    H ⊆ D (1,646,213 instances, 1,882,885 optimal Y*, 12,426,745 pairs), and on 24,000 random sparse or
    tree-like instances with 7–14 vertices (1,016,936 pairs);
  - Lemma 3.1 on 3,000 dense instances, and Theorem 3.4 (own Dreyfus–Wagner on G_C) against brute force on 401
    dense instances (183 clusters joined by long paths, opt up to 14);
  - Lemmas 4.1–4.4 (13 pairs (q,d); 3,000 product pairs; 200 dense instances; 4,635 (formula, k) pairs), the
    chain on 40 formulas, the size bounds up to v = 10^6, the previous Remark 4.5 and the ε = 1/|N|
    construction, and the gadget with one set per one-dimensional subspace.

  The recorded output was reproduced in a scratch copy on 2026-09-29 (identical apart from the timing). The
  referee also reran the finder, lead and first-referee scripts, with identical outputs apart from timings.
- **Lead, second revision** (`lead/rem45_distinct_check.py`, standard library only, a few seconds, 0 failures).
  It checks the revised, distinct-set Remark 4.5 on 300 random set systems (157 of them with repeated members
  before de-duplication): distinct sets, the projective count, ε-density, covering number min(τ(U,𝓕), d), and
  the bound on q^d. It also runs the chain 3-CNF → block encoding → distinct-set dense Set Cover on 40 formulas;
  16 of the block families had repeated sets before de-duplication.

The computations are evidence only; the proofs are complete by hand.

## Independent adversarial audit
Verdict (2026-09-29): **PAPER_CANDIDATE**; correct: yes; answers the question as intended: yes.

| Item | Verdict |
|---|---|
| Source fidelity (p. 1532, pp. 1492–1495; PDF hash matched) | CONFIRMED |
| Lemma 1 (hubs), Claim 2.3 (7r − 6), Lemma 2, Theorem 1, Corollary 1 | CONFIRMED (checked by hand, no gaps) |
| Lemmas 4–7 and Theorem 3 (ETH, W[2], no FPTAS) | CONFIRMED |
| Computations (finder's rerun; referee's own scripts) | CONFIRMED |
| Novelty | open in 2004, 2015 and 2020; the result is new as far as can be found; the technique is standard |

The six required fixes, and how they were applied:
1. **Cite the Hauptmann–Karpinski compendium.** Applied: [HK15], revision 288 of 2015-04-27, entry 1.6. It was
   fetched anonymously and its comment was confirmed.
2. **Credit Megiddo–Vishkin 1988 and Papadimitriou–Yannakakis 1996, check the dense Set Cover bound, and rest the
   novelty on the Steiner resolution.** Applied.
   - Both papers are credited, and Lemma 4.4 is labelled "after [MV88]".
   - One web search and arXiv API searches found no explicit ETH lower bound for ε-dense Set Cover for all
     ε < 1. The paper says it "may well be folklore" and claims no novelty for the lower-bound technique.
   - The novelty claim rests on the resolution of the Steiner question, through Lemma 3.3 and the gadget. (After
     the second audit this was made more modest: the new ingredient is Lemma 3.3 only; see fix 2 below.)
3. **State Lemma 2 in its simpler equivalent form.** Applied: it is now Lemma 3.3,
   |Y* ∩ D| ≤ |H| + 2r − 2 for any H ⊆ D, with the remark that density is used only in Lemma 3.1.
   - The optional sharper bound 2r − 2 is proved in Lemma 3.2, with a new short proof.
   - That proof was written after the referee's review. It was checked by the lead's exhaustive and random
     tests, and it is consistent with every referee test.
4. **Print the instance count in `test_small.py`.** Applied; the pre-audit script and output are preserved.
5. **Keep the hypotheses separate.** Applied in the abstract, Corollary 1.3, the "Scope and priority" paragraph
   and RESULT.md.
6. **Publish a preprint before any HF status change, and report the result as conditional.** Noted. This package
   is the preprint; no status change has been made.

### Second independent audit (referee 2, 2026-09-29)
Verdict: **correct and publishable after minor fixes; not fatal.** The referee checked every proof line by line
and found no gap, and wrote independent code (0 failures).

| Area | Verdict |
|---|---|
| Statement fidelity (OWR 2004/28 fetched through the DOI; same SHA-1 as the local copy) | CONFIRMED |
| Proofs (Obs. 2.1, Lemmas 3.1–3.3, Thm 3.4, Cor. 3.5, Rem. 3.6, Lemmas 4.1–4.4, Thm 1.2, Cor. 1.3, Rem. 4.5, §5) | CONFIRMED; Remark 4.5 held only for multi-families as written (fix 3) |
| Computations (independent code; finder, lead and first-referee scripts rerun) | CONFIRMED |
| Novelty | no prior exact-complexity result for fixed ε found; CKSV11, Thm 5.2 (NP-hardness at polynomially small density) was not credited (fix 1) |
| Presentation / house style | good; a few wording and bibliography fixes needed |
| Release package | complete and consistent; to be regenerated after the fixes |

All six required fixes were applied:
1. **Credit CKSV11, Theorem 5.2.** Applied in the Introduction, in "Open questions", in "Scope and priority" and
   in this report. Steiner Tree is APX-hard, hence NP-hard, on graphs in which every vertex has degree at least
   |V∖S|^{1−δ}. In those instances every terminal has at least |N|^{1−δ} non-terminal neighbours, so the exact
   problem is NP-hard at density ε = |N|^{−δ}. This was checked on p. 18 of arXiv:1011.0078v2. The ε = 1/|N|
   construction is kept only as a parenthetical illustration. The picture is now stated: quasi-polynomial for
   ε ≥ 1/polylog n, NP-hard for ε = n^{−δ}, open in between.
2. **Novelty sentence.** Applied. It now reads: the new ingredient is Lemma 3.3, and the gadget of Lemma 4.1 is an
   elementary linear-algebra construction that we did not find used for this purpose.
3. **Remark 4.5.** Applied by removing the repetitions. There is one gadget set per one-dimensional subspace of
   F_q^d, 𝓕 is de-duplicated (the block encoding can produce repeated sets), and d ≥ k + 1 is taken least with
   (q^d − 1)/(q − 1) ≥ εm/(ρ − ε), instead of R copies. The paper proves distinctness, density, the covering
   number and the size bound.
   - The referee's suggested condition q^d − 1 ≥ εm/(ρ − ε) was strengthened by the factor q − 1, because only
     (q^d − 1)/(q − 1) sets remain after the repetitions are removed.
   - For q ≥ 3 the weaker condition can fail. For example, with q = 5, ε = 0.7 and m = 3 it gives d = 2 and
     |P| = 6, and each point then lies in 5 < 0.7 · 9 sets.
   - The revised construction is checked by `lead/rem45_distinct_check.py`.
4. **Unread related sources.** Applied in "Scope and priority", in the Introduction and in this report. They are
   Hauptmann's 2004 Bonn dissertation (zbMATH document 5042868, Zbl 1103.90085; the full text was not accessible)
   and Bar-Yehuda–Kehat, JCSS 69 (2004) 547–561, doi:10.1016/j.jcss.2004.03.006. The latter is cited next to the
   "may well be folklore" sentence as a related source that was not consulted. Both sets of metadata were
   confirmed by anonymous Crossref and zbMATH API requests, which are logged.
5. **Bibliography.** Applied. The [KKP04] note now reads pp. 1531–1532 (Problem 3 on p. 1532). In [HK15] the stray
   "Editors." is now "M. Hauptmann and M. Karpinski (editors)".
6. **Regenerated release package.** Applied.
   - The paper was rebuilt with tectonic: no errors or warnings, and no overfull or underfull boxes. All 11 page
     images were inspected.
   - main.tex, references.bib and paper.pdf were copied into release/, and this report was updated.
   - The referee's script and its output were added under `reproducibility/referee2/` and described in
     README.md, because the paper's Verification paragraph now cites them.
   - source.zip was rebuilt, and the zenodo/ copies with their sha256, size and md5 were refreshed. The abstract
     is unchanged, so the Zenodo description is unchanged.

The optional suggestions were also applied:
- (a) "We answer the question conditionally, …";
- (b) the justification of M ≤ 8v³;
- (c) N ≠ ∅ is noted as an addition;
- (d) val(C) is finite;
- (e) the second referee's checks are listed in the Verification paragraph.

The pre-revision source is preserved as `paper/main_v1_prereferee_2026-09-29.tex`.

## Relation to the literature, novelty and scope
- **Searches (September 2026).**
  - Databases: arXiv (API), Crossref, OpenAlex and zbMATH.
  - Web: one search each by the finder, the auditor, the paper author and the second referee. Every request is
    logged in `queries.log` of the working folder.
  - The question is recorded as open in OWR 2004, in the Hauptmann–Karpinski compendium (2015) and by
    Karpinski–Lewandowski–Meesum–Mnich (arXiv:2004.14102, 2020, p. 2).
  - OpenAlex records no citations of the 2020 paper.
  - No exact complexity result for ε-Dense Steiner Tree with fixed ε was found. For polynomially small density,
    NP-hardness follows from CKSV11, Theorem 5.2 (see below).
- **Prior work credited.**
  - Karpinski–Zelikovsky (PTAS; exact m^{O(log n)} algorithm for dense Set Cover).
  - Cardinal–Karpinski–Schmied–Viehmann (subdense instances; and, in Theorem 5.2 of the full version,
    APX-hardness, hence NP-hardness, of Steiner Tree at polynomially small density |N|^{−δ}. Earlier text said
    only that later work concerns approximation; this hardness result is now acknowledged).
  - Hauptmann (2007, 2013).
  - Megiddo–Vishkin (the block encoding), Papadimitriou–Yannakakis (LOGSNP), KLMM (a root vertex in a
    Set Cover reduction), Dreyfus–Wagner, Impagliazzo–Paturi–Zane (ETH), Downey–Fellows (W[2]).
- **Caveats.**
  - The full texts of Karpinski–Zelikovsky 1998, Hauptmann 2007/2013, Megiddo–Vishkin 1988 and
    Papadimitriou–Yannakakis 1996 were not read. Statements about them follow CKSV, OWR, the compendium and the
    standard secondary literature.
  - Not consulted either:
    - Hauptmann's 2004 Bonn dissertation (zbMATH document 5042868). It treats dense Steiner problems, and its
      summary mentions approximation schemes. The repository serves a bot-check page, which was not bypassed.
    - Bar-Yehuda–Kehat, "Approximating the dense set-cover problem", JCSS 69 (2004) 547–561,
      doi:10.1016/j.jcss.2004.03.006 (publisher page 403). It is relevant to the "may well be folklore" sentence
      on dense Set Cover.
  - The negative search is not a proof of priority.
- **Scope.**
  - The lower bound holds for each fixed ε ∈ (0,1).
  - Density as a function of n: quasi-polynomial for ε ≥ 1/polylog n (Remark 3.6); NP-hard for ε = n^{−δ}
    (CKSV11, Thm 5.2, not this paper); open in between, e.g. ε = 2^{−√(log n)}. For ε ≥ n^{−o(1)} the algorithm
    runs in time 2^{n^{o(1)}}, so NP-hardness there would contradict ETH.
  - Novelty: the new ingredient is Lemma 3.3. The gadget of Lemma 4.1 is elementary linear algebra that was not
    found used for this purpose. No novelty is claimed for the lower-bound technique.
  - The dependence of the exponent on ε remains open: the upper bound has exponent O(log n/ε), while the lower
    bound only excludes exponents o(log N).
  - Whether the parameterized problem lies in W[2] was not examined.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/