Pith. sign in

REVIEW 3 major objections 4 minor 12 references

When does FTP become FPT?

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

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

Pith's one-line read Fault-Tolerant Path is fixed-parameter tractable when parameterized by the number of vulnerable or safe edges, and W[1]-hard when parameterized by the budget, leaving only the redundancy parameter k open.

desk verdict Solid classification of FTP with one fixable gap in the Biclique reduction; worth a serious referee. read the letter →

arxiv 2506.17008 v1 pith:ONY3O4WP submitted 2025-06-20 cs.DS cs.DM

Matthias Bentert , Fedor V. Fomin , Petr A. Golovach , Laure Morelle This is my paper · ORCID
classification cs.DScs.DM
keywords fault-tolerantpathparameterizedcomplexityfixed-parametertractabilityW[1]-hardnessdirectedsteinerlinkagekernelizationlowerboundssafeandvulnerableedgesbicliquereduction
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 when the Fault-Tolerant Path problem, in which a budget-constrained subgraph must survive the deletion of any k vulnerable edges, becomes fixed-parameter tractable. It answers the question for nearly every natural parameter: the problem is FPT when parameterized by the number of vulnerable edges |U| or the number of safe edges |S|; it is in XP but W[1]-hard for the budget ℓ and for the counts p and q of solution edges; and it is already NP-hard when the budget exceeds the minimum-cost (k+1)-flow by just one unit. The only parameter whose exact status remains open is the required redundancy k.

What carries the argument

The proof rests on three components. First, a new intermediate problem, Directed Steiner Linkage, asks for a cheapest edge set connecting each of k terminals to its matched partner; the paper proves this problem FPT in $2^{{O(k \log k)}}$ $n^{3}$ time by guessing the structure of a forest solution and finding it by color-coding. Second, a flow-based reformulation (Lemma 1) shows that any FTP solution is equivalent to k+1 s-t paths that pairwise intersect only in safe edges; this underlies the algorithms and the definition of the below-guarantee parameter b = C − ℓ. Third, a reduction from Biclique establishes W[1]-hardness for ℓ even at b=1, and a counting argument with the sets X and Y forces the existence of a K_{d,d} in any solution. The kernel lower bounds come from polynomial parameter transformations from Steiner Tree (for |U|) and Hitting Set (for |S|).

What would settle it

Brute-force all bipartite graphs on 4+4 vertices with fewer than 12 edges and check, for each, whether the constructed FTP instance with ℓ=11 and k=3 is a yes-instance exactly when the graph contains K_{2,2}. Any mismatch invalidates the reduction in Theorem 4 and hence the claimed W[1]-hardness for ℓ.

Watch

Extended reading notes

Core claim

In the paper's own framing, Fault-Tolerant Path (FTP) admits a $2^{{O(|U| \log |U|)}}$ $n^{3}$ algorithm when parameterized by the number of vulnerable edges in the input graph, and a $2^{{|S|}}$ $m^{{1+o(1)}}$ algorithm when parameterized by the number of safe edges. Symmetrically, FTP is W[1]-hard when parameterized by the budget ℓ even when the below-guarantee parameter b = C − ℓ equals 1, where C is the minimum cost of a (k+1)-flow; under the ETH this rules out f(ℓ) $n^{{o(\sqrt[4]{ℓ}}$)} algorithms. The paper also rules out polynomial kernels for the parameters |U| and |S|. Together these results provide an almost complete classification of the FTP parameterized complexity landscape, with only the redundancy parameter k left open.

Load-bearing premise

The W[1]-hardness proof assumes the Biclique input graph has at least $3d^{2}$ edges; the reverse direction needs an edge outside the constructed solution to replace a three-edge vulnerable path, and the paper does not justify why Biclique instances with fewer edges can be ignored.

Editorial extensions

If this is right

  • When an instance has only |U| vulnerable edges, FTP can be solved in 2^{O(|U| \log |U|)} n^3 time, so the vulnerable-edge count is a practical parameter for real networks.
  • When |S| is small, the problem is FPT in 2^{|S|} m^{1+o(1)}, meaning safe edges can be exhaustively guessed and the rest solved by minimum-cost flow.
  • For the budget ℓ, the problem is W[1]-hard even when b=1, so no f(ℓ) n^{O(1)} algorithm exists unless the W-hierarchy collapses; the ETH lower bound makes this quantitative.
  • FTP admits no polynomial kernel for |U| or |S|, so instances cannot be compressed to size polynomial in these parameters, even though the problems are FPT.
  • The only remaining open case is the parameter k; the paper leaves open whether k=2 is polynomial-time solvable or NP-hard.

Reading between the lines

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

  • The flow-based view suggests a natural extension: replacing the (k+1)-flow optimum C by any lower bound on the cost of a fault-tolerant solution may yield new hard parameters, since b=1 already captures Biclique hardness.
  • The new Directed Steiner Linkage problem is likely to find use in other fault-tolerant network design problems, where solutions decompose into paths meeting only at safe edges; the forest-guessing technique transfers.
  • If the open k case turns out to be para-NP-hard, the landscape would be complete; the techniques used here—especially the edge-counting argument around X and Y—might be sharpened to test k=2.
  • The kernel lower bounds indicate that preprocessing for |U| and |S| cannot go beyond trivial compression, so practical heuristics should focus on the FPT algorithms themselves rather than kernelization.
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 / 4 minor

Summary. The paper studies the parameterized complexity of Fault-Tolerant Path (FTP), where edges are partitioned into safe and vulnerable edges, and the task is to find a low-cost subgraph that still contains an s-t path after any k vulnerable edges are deleted. The authors analyze the parameters k, ℓ, |S|, |U|, p, q, the above-guarantee parameter a = ℓ − dist(s,t), and the below-guarantee parameter b = C − ℓ. They provide FPT algorithms for |U| and |S|, XP algorithms for q and p, W[1]-hardness for ℓ (even with b = 1), para-NP-hardness for b, and kernelization lower bounds for |U| and |S|, leaving only the parameter k open. A key technical tool is a newly introduced problem, Directed Steiner Linkage, which is shown to be FPT in the number of terminals. The paper's main positive results are obtained via reductions to Directed Steiner Linkage and to min-cost flow, while the hardness results use reductions from Biclique, Steiner Tree, and Hitting Set.

Significance. If the results hold, the paper gives an almost complete parameterized classification of a natural and increasingly studied fault-tolerance model, which is a valuable contribution. The introduction of Directed Steiner Linkage and its FPT algorithm are likely to be useful beyond this paper. The algorithmic sections (Theorems 1–3) are coherent and use standard, well-chosen techniques: structural forest lemmas, color coding, and almost-linear min-cost flow. The hardness reductions target the right known hard problems. However, the proof of the main hardness theorem (Theorem 4) contains an unproven sparseness assumption and an unsupported replacement argument in the reverse direction, and the proof of Proposition 3 contains a false replacement claim. These gaps affect load-bearing claims (W[1]-hardness for ℓ, the ETH lower bound, and the kernel lower bound for |S|), so the paper requires careful revision before it can be accepted.

major comments (3)
  1. [Theorem 4, first paragraph of the proof] The proof assumes without loss of generality that |E| ≥ 3d^2, and this assumption is used in the reverse direction to guarantee an edge {x,y} of G that is not contained in the constructed FTP solution. No justification is given for discarding instances with fewer than 3d^2 edges. The WLOG is salvageable by observing that a Biclique instance with |E| < 3d^2 has O(d^2) non-isolated vertices and can be solved by brute force in 2^{O(d log d)} time, but as written the reduction does not cover sparse inputs and therefore does not constitute a complete reduction from Biclique.
  2. [Theorem 4, reverse direction, EP-path replacement] The step that replaces an entire three-edge EP path by the path Q=(v,x,y,t) and asserts that 'the obtained set of edges forms a solution' is not justified. If a deletion set in the new solution contains the new vulnerable edge {x,y}, then Q is broken, and the original EP path has been removed, so the fault-tolerance property is not obviously preserved. The proof should either prove this replacement property or replace the step with a counting argument showing that any solution of size at most 3d^2−1 cannot contain a complete EP path; the latter is straightforward from the cut condition |C'|+t ≥ d^2 together with the edge budget. This gap is load-bearing for the W[1]-hardness of ℓ and for the ETH lower bound.
  3. [Proposition 3, paragraph beginning 'We assume without loss of generality...'] The claimed WLOG replacement is false. In the constructed graph with U={a,b}, F={F1,F2}, F1={a,b}, F2={a}, d=1, ℓ=5, and k=1, the edge set K={s,a}, {t,F1}, {t,F2}, {a,F1}, {b,F1} is a valid FTP solution. Here b is connected to s via a and F1 without using the safe edge {s,b}. Replacing {b,F1} by {s,b} yields K'={s,a}, {s,b}, {t,F1}, {t,F2}, {a,F1}, which ceases to be a solution: deleting the vulnerable edge {a,F1} leaves no s-t path because no cross edge from U to F remains. The proof of the kernel lower bound for |S| therefore needs a different argument to extract a hitting set of size at most d.
minor comments (4)
  1. [Abstract and Section 1.2] There are several spacing and typographical errors, including 'F ault-Tolerant Path' in the abstract and 'Bentert at al.' in the Related Work section.
  2. [Theorem 4, construction] The path P has 2d^2−2d−1 edges, which is negative for d=1; the proof should either handle d=1 separately (it is a trivial Biclique instance) or explicitly assume d≥2.
  3. [Theorem 2, proof] The budget for the constructed Directed Steiner Linkage instance is not specified explicitly; it should be stated as ℓ minus the total weight of the guessed vulnerable edges.
  4. [Lemma 1] The displayed summation in the statement of Lemma 1 is typeset incorrectly; it should read ∑_{e∈S∩(⋃ E_i)} w(e) ≤ ℓ.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: central claims are derived from external hardness results, standard algorithms, and from-scratch reductions; the flagged |E|>=3d^2 WLOG is a correctness gap, not circularity.

full rationale

The paper's derivation chain is self-contained. Theorem 2 obtains FPT for |U| by exhaustively guessing vulnerable edges in an optimal solution (enumeration, not fitted prediction) and reducing to Directed Steiner Linkage, whose FPT algorithm is proven from scratch via a flow/cycle lemma, forest-structure bounds, and color coding. Theorem 3 guesses safe edges and uses min-cost flow. The hardness results are standard parameterized reductions from external W[1]-hard Biclique and external no-polynomial-kernel results for Steiner Tree and Hitting Set, with explicit equivalence proofs. Cited prior work by the same authors (reference [5]) appears only as related work and is not load-bearing; the load-bearing Lemma 1 comes from the external paper [2]. The suspicious WLOG |E|>=3d^2 in Theorem 4 is a potential correctness gap in the reverse direction (the replacement of an EP path needs an unused edge of G), but it is not circular: it is an internal combinatorial step and does not assume the target result. No quantity is fitted to data, no prediction is renamed as a result, and no central assumption is imported solely from the authors' own prior work. Thus the paper merits a circularity score of 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The central results rest on standard external hardness and algorithmic results plus the newly introduced Directed Steiner Linkage. No numeric free parameters are fitted; all parameters are input integers.

assumptions (6)
  • domain assumption Biclique is W[1]-hard parameterized by d and has no f(d)n^{o(sqrt d)} algorithm under ETH (Lin [11]).
    Used as the source problem in the reduction for Theorem 4.
  • domain assumption Steiner Tree parameterized by the number of terminals has no polynomial kernel (Cygan et al. [9]).
    Used in Proposition 2 to prove no polynomial kernel for parameter |U|.
  • domain assumption Hitting Set parameterized by the size of the universe has no polynomial kernel (Dom et al. [10]).
    Used in Proposition 3 to prove no polynomial kernel for parameter |S|.
  • standard math Color coding finds a minimum-cost copy of a bounded-size pattern in 2^{O(k)} n^{O(1)} time (Alon, Yuster, Zwick [3]).
    Used inside the FPT algorithm for Directed Steiner Linkage in Theorem 1.
  • standard math Minimum-cost (k+1)-flow can be computed in m^{1+o(1)} time (van den Brand et al. [7]).
    Used in Theorem 3 and in the definition of the below-guarantee parameter b.
  • standard math The number of forests on at most N labeled vertices is at most (4k)^{4k} (Takács [12]/Cayley formula).
    Used to bound the number of guesses in Theorem 1.
invented entities (1)
  • Directed Steiner Linkage problem
    purpose: Auxiliary problem to which FTP is reduced after guessing vulnerable or safe edges; the paper proves it FPT in the number of terminals.
    The problem is defined in this paper and is not used outside it; the authors themselves only suspect it is of independent interest. No external benchmark or application is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When does FTP become FPT?." pith.science (2026). https://pith.science/paper/ONY3O4WP

@misc{pith2026250617008,
  author       = {Pith},
  title        = {Pith review of: When does FTP become FPT?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ONY3O4WP}},
  note         = {Machine review of arXiv:2506.17008}
}
read the original abstract

In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers k and \ell. The task is to decide whether there exists a subgraph H of G with total cost at most \ell such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include: the number of vulnerable edges in the input graph, the number of safe (i.e, invulnerable) edges in the input graph, the budget \ell, the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters.

Figures

Figures reproduced from arXiv: 2506.17008 by the authors.

Figure 1
Figure 1. Overview of our results. An edge between two parameters [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The graph constructed in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. The sets X, Y, X′ , and Y ′ constructed in Theorem 4. The three dashed lines corresponds to SXY ∪ SXY ′, SXY ∪ SX′Y , and SXY ∪ SX′Y ′. of vulnerable edges in K. Because K is a solution, we have that |SXY | + |SXY ′| ≥ d 2 , |SXY | + |SX′Y | ≥ d 2 , and |SXY | + |SX′Y ′| ≥ d 2 , as depicted in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: An example of the construction behind the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: The graph G in the proof of Proposition 3. Safe edges are represented in blue and vulnerable edges in black. For the other direction, assume that there is a solution of size ℓ = 2|F| + d in the con￾structed instance of Fault-Tolerant Path. Then, this solution contains …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Adjiashvili, F

    D. Adjiashvili, F. Hommelsheim, and M. M \" u hlenthaler , Flexible graph connectivity , Mathematical Programming, 192 (2022), pp. 409--441

    work page 2022

  2. [2]

    Adjiashvili, F

    D. Adjiashvili, F. Hommelsheim, M. M \" u hlenthaler, and O. Schaudt , Fault-tolerant edge-disjoint s-t paths -- beyond uniform faults , in Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory ( SWAT ), Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022, pp. 5:1--5:19

    work page 2022

  3. [3]

    N. Alon, R. Yuster, and U. Zwick , Color-coding , Journal of the ACM , 42 (1995), pp. 844--856

    work page 1995

  4. [4]

    Bansal, J

    I. Bansal, J. Cheriyan, L. Grout, and S. Ibrahimpur , Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions , in Proceedings of the 50th International Colloquium on Automata, Languages, and Programming ( ICALP ), Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023, pp. 15:1--15:19

    work page 2023

  5. [5]

    Bentert, J

    M. Bentert, J. Schestag, and F. Sommer , On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model , in Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC), Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023, pp. 4:1--4:12

    work page 2023

  6. [6]

    S. C. Boyd, J. Cheriyan, A. Haddadan, and S. Ibrahimpur , Approximation algorithms for flexible graph connectivity , in Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ( FSTTCS ), Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021, pp. 9:1--9:14

    work page 2021

  7. [7]

    Brand van den Brand , L

    J. Brand van den Brand , L. Chen, R. Peng, R. Kyng, Y. P. Liu, M. P. Gutenberg, S. Sachdeva, and A. Sidford , A deterministic almost-linear time algorithm for minimum-cost flow , in Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , IEEE , 2023, pp. 503--514

    work page 2023

  8. [8]

    Chekuri and R

    C. Chekuri and R. Jain , Approximation algorithms for network design in non-uniform fault models , in Proceedings of the 50th International Colloquium on Automata, Languages, and Programming ( ICALP ), Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023, pp. 36:1--36:20

    work page 2023

Show all 12 references
  1. [9]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh , Parameterized Algorithms , Springer, 2015

    2015

  2. [10]

    M. Dom, D. Lokshtanov, and S. Saurabh , Incompressibility through colors and ids , in Proceedings of the 36th International Colloquium on Automata, Languages and Programming ( ICALP ), Springer, 2009, pp. 378--389

    2009

  3. [11]

    Lin , The parameterized complexity of the k -biclique problem , Journal of the ACM , 65 (2018), pp

    B. Lin , The parameterized complexity of the k -biclique problem , Journal of the ACM , 65 (2018), pp. 34:1--34:23

    2018

  4. [12]

    Tak \'a cs , On C ayley's formula for counting forests , Journal of Combinatorial Theory, Series A, 53 (1990), pp

    L. Tak \'a cs , On C ayley's formula for counting forests , Journal of Combinatorial Theory, Series A, 53 (1990), pp. 321--323

    1990

Pith tools

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