# Verification report — OWR-1111-001 (Krause: complexity of Blocking Shortest Paths for three terminals)

Verification date: 2026-10-13 (UTC; the runs were made on 13 and 14 October, local time).

**Verdict.** The note gives a **complete answer** to the question of the record: for triangle instances of Blocking
Shortest Paths (the three pairs of three given vertices; unit lengths, costs positive integers or all equal to 1) the
problem is **NP-hard**, and the decision problem is NP-complete.
- **Theorem 1.3.** NP-completeness for (a) bipartite graphs with edge costs and the three terminals pairwise at
  distance 4, and (b) bipartite graphs with unit costs and the terminals pairwise at distance 6.
- **Theorem 1.4 (the identities).** For a graph H = (U, D) with positive integer weights and three terminals,
  opt BSP(Γ(H)) = 2 w(D) + mwc(H) (Proposition 3.2), and for unit weights opt BSP(Γ'(H)) = 2 |D| + mwc(H)
  (Proposition 4.2), where Γ(H) has a hub x(i,e) for each terminal index i and each edge e of H, a light edge
  r_i x(i,e) of cost w(e) and heavy edges (cost 3 w(D) + 1) from the hub to the ends of e, and heavy edges joining
  r_i to the terminal a_i of H through a vertex p_i; Γ'(H) replaces the heavy edges by bundles of K = 3|D| + 1
  internally disjoint paths. A blocking set of cost 2 w(D) + k gives a three-terminal cut of weight at most k.
- **What is used from the literature.** The NP-hardness of the three-terminal cut problem, with unit weights
  (Dahlhaus, Johnson, Papadimitriou, Seymour, Yannakakis, STOC 1992, Theorem 3, and the remark in its Section 3 that
  k = 3 suffices). The note states Theorem 2.2 with the bound k ≥ 0 and a remark on parallel edges.
- **Not new.** The problem, the notion of a triangle instance and the question are Krause's; the hardness of the
  three-terminal cut problem is due to Dahlhaus et al.; the replacement of an edge of cost c by c paths of length 2
  (Remark 5.1) is Krause's. The proofs of the note contain no new hardness argument of their own.
- **New, to our knowledge and relative to the literature found.** The answer for triangle instances (NP-hard in
  both versions), by a reduction of the note's own.
- **Limits.** Planar triangle instances are not settled (the three-terminal cut problem is polynomial for planar
  graphs; the graphs Γ(H) are not planar in general). No statement on approximability is made (the reduction keeps
  the additive error only; a conditional MAX SNP-hardness via an L-reduction was suggested by a verification run but
  depends on the structure of the unit-weight instances of Dahlhaus et al., whose full paper was not read). Triangle
  instances with the terminals at distance 2 or 3 were not examined. The full version of the paper of Dahlhaus et
  al. (SIAM J. Comput. 23 (1994)) was not accessible to us; the extended abstract (STOC 1992) was read.

## Statement check
- The record: "Given an undirected graph, with or without edge costs, and three vertices r,s,t, determine the
  complexity of finding a minimum-cost edge set whose deletion increases each of the distances d(r,s), d(r,t), and
  d(s,t) by at least 1." — open problem (1) of Krause's abstract (Oberwolfach Report 50/2005, pp. 2856–2858),
  verbatim in substance; the thesis (Section 4.3) leaves the complexity of triangle instances undetermined, and the
  summary of the thesis in zbMATH (Zbl 1238.05002) names this as the only open case of its chapter on complexity.
- Definition 1.1 of the note is Krause's BSP (unit lengths, distance = number of edges, positive costs, "blocks all
  shortest paths" = "increases the distance by at least 1"); no alternative reading (lengths equal to costs,
  multigraphs, adjacent terminals, increase by exactly 1, finer complexity classes) changes or trivialises the
  answer (checked by the first and third runs).
- The record's literature assessment says the complexity is open "including the directed-graph variant"; the
  directed triangle case is NP-hard by Krause's thesis (Theorem 9.3), as the note states in Section 1.4.

## Verification runs (three independent AI-assisted runs; none saw the others' reports)
- **Run A (statement and proofs).** Compared the definitions with the abstract and the thesis; re-derived Lemma 2.1,
  Lemma 3.1, Proposition 3.2, Lemma 4.1, Proposition 4.2 and Remark 5.2 from scratch; probed the boundary cases
  (isolated vertices and terminals, single edge, adjacent terminals, components without terminals, heavy edges,
  the forcing of F_L, the counts); hand examples (star: 8 = 2·3 + 2; triangle: 9 = 2·3 + 3); own program (integer
  program, enumeration) on 15 further cases. No gap. Required: the case k > w(D) in the last sentence of
  Theorem 1.4 (D itself is a cut), the edgeless H in the proof of Theorem 1.3, citations of the extended abstract by
  the correct sections, small wording. All applied.
- **Run B (own computation and literature).** Own solvers (an exact hitting-set computation over all enumerated
  shortest paths, a branch and bound, an integer program over paths; mwc from the definition by components and by
  labellings) on all connected H with 3 to 7 vertices and all choices of three terminals (2476 + 29855 instances
  with unit weights, the same with random weights), 137 disconnected H, 300 random weighted H; Γ'(H) on 222 + 734 +
  117 + 60 instances; the distance-8 variant on 222; with K = 1 the identity fails (54 failures), with K ≥ 2 never.
  Remark 5.2 on 60 327 random weighted edges and by hand. The note's scripts: no vacuous test; recorded counts
  reproduced. Sources: the STOC 1992 extended abstract (Theorem 3, the k = 3 remark, Theorem 5) quoted accurately;
  the thesis sentences and the bibliography checked; the thesis DOI resolves. Literature (Crossref, OpenAlex, arXiv,
  zbMATH Open): no work determines the complexity of triangle instances; the thesis has no citing work. Required:
  citations by subsection and page, a remark on parallel edges. All applied.
- **Run 2 (the third run, on the final text).** Re-derived every statement and proof from the definitions, with the
  boundary cases (isolated vertices or terminals, parallel edges, the threshold k ≤ w(D), K = 3|D| + 1, the level
  argument of Lemma 4.1); found one boundary case to repair (an edgeless H with a negative bound k; now k ≥ 0 in
  Theorem 2.2). Compared the sentences about the sources with the abstract, the thesis, the extended abstract and
  the record, and the bibliography with Crossref and DataCite. Own program (shortest-path enumeration and an exact
  hitting-set computation, cross-checked by a branch and bound and by an integer program over paths): Γ(H) on all
  1416 instances with connected H on 3 to 5 vertices and all ordered choices of terminals, each with unit weights
  and two random weightings, and 822 instances with disconnected H; Γ'(H) on 529 instances. All identities held;
  every optimal blocking set consisted of light edges; the labelling of Proposition 3.2(b) gave a cut of the
  predicted weight. Re-ran test_reduction.py from a copy: recorded output reproduced. Wording scan: clean.

## Readings
- Read: Krause's abstract (Oberwolfach Report 50/2005, pp. 2856–2858, publisher's file); Krause's thesis (TU
  Braunschweig 2006, file of the German National Library): Chapter 1, Sections 3.2, 3.5, 4.1, 4.3, 4.4, 4.5, the
  statements and proofs of Corollaries 4.1 and 4.2, Sections 7.1, 9.1 and the beginning of 9.2; the zbMATH summary
  of the thesis; the STOC 1992 extended abstract of Dahlhaus et al. (introduction with Theorems 1–5, the beginning
  of Section 3, the subsection "Near-Optimal Multiway Cuts", the concluding section), in a copy of the publisher's
  file; arXiv:1611.08809v1, proof of Theorem 8 (no longer needed).
- Not read: the SIAM 1994 full version of Dahlhaus et al. (not accessible to us); Bienstock–Diaz 1993 (cited as in
  the sources); the remaining parts of the thesis.

## Relation to the literature, novelty and scope
- The question: Krause 2005/2006 (abstract, open problem (1); thesis Section 4.3). The thesis proves: star
  instances polynomial (Theorem 4.1); two disjoint pairs NP-hard, even for grid graphs of maximum degree 3 and for
  planar bipartite graphs with unit costs (Theorem 4.2, Corollaries 4.1, 4.2); the directed triangle case NP-hard
  (Theorem 9.3).
- Dahlhaus et al. (STOC 1992) observe in their concluding section that the multicut problem for the three pairs of
  three terminals (all paths cut) is the three-terminal cut problem; for BSP (shortest paths only) a reduction of
  its own is needed.
- Searches (13 October 2026, lead and runs): arXiv API, zbMATH Open, Crossref, OpenAlex, Semantic Scholar (partly),
  web; works citing the thesis: none; related papers on length-bounded cuts, shortest path interdiction, force path
  cut, hitting geodesic intervals: none settles triangle instances. A search that finds nothing is not a proof of
  novelty; no priority is claimed.

## Public release and license
Unrefereed preprint, CC BY 4.0. Files: paper (PDF), source archive (LaTeX source, this report, reproducibility
package with the programs of the note and of two of the verification runs), verification report. AI-assisted tools
supported research, computation, proof development and manuscript preparation; the author is responsible for all
claims.