An arXiv preprint has drawn a sharp line between tractable and hard cases of Seg-Agony, a decision problem built around temporal directed graphs. It gives a polynomial-time algorithm for two ranks, but reports that the unweighted version is NP-complete with three ranks and one change point. It also reports that unweighted Seg-Agony is NP-hard with four ranks, one change point, zero target agony, a lifetime of 11 and an underlying DAG.
Those are proof-based complexity results, not measurements from an empirical sample. The analyzed units are formal Seg-Agony decision instances consisting of a temporal weighted digraph and the integers k, ℓ and α. In the paper’s notation, n is the number of vertices, k the number of ranks, ℓ the number of change points, α the target agony and τ the lifetime. The study asks how the computational classification changes as those quantities vary.
A broader tractability result
In parameterized-complexity language, FPT, short for fixed-parameter tractable, and XP are labels for different running-time guarantees. The paper classifies Seg-Agony as FPT for the combined parameter n + ℓ and as XP for n alone. In the supplied analysis, that means the n-only result should not be read as an FPT classification.
For n + ℓ, the algorithm uses dynamic programming over all possible rank ℓ-segmentations—a way of reusing solutions to smaller subproblems while testing possible segmentations. The reported running time is τ (ℓn)^O(n) log W. The expression is an upper bound from the analysis, not a measured speed on a benchmark.
The two-rank case is more direct. For k = 2, Seg-Agony is solvable in O(n^2 τ ℓ log(nτW)) time. That is a polynomial-time algorithm, putting this fixed-rank setting on the tractable side of the paper’s map.
Three ranks change the picture
Three ranks produce a more complicated boundary. When k = 3, the target agony is zero, α = 0, and there is one change point, ℓ = 1, Seg-Agony is polynomial-time solvable. But the unweighted version is NP-complete for k = 3 and ℓ = 1.
NP-complete is a warning label in complexity theory: it signals that a general polynomial-time solution is not known for the problem under the usual assumptions. The distinction here matters because the polynomial result is tied to zero agony, while the hardness result concerns the unweighted case; they do not describe the same set of inputs.
For k = 3 and ℓ = 1, the authors also place Seg-Agony in XP when α is the parameter, with a running time of (τ n)^α · n^O(1). That is a parameterized upper bound, but it is not an FPT result in α. The supplied analysis explicitly leaves fixed-parameter tractability for the unweighted three-rank case as an open question.
Hardness under tight restrictions
The four-rank result pushes the hard boundary into a tightly restricted case. Unweighted Seg-Agony is NP-hard for k = 4, ℓ = 1, α = 0 and τ = 11, even when the underlying digraph is a DAG, meaning it has no directed cycles.
The classifications are established through reductions rather than network trials. For the three-rank analysis, the paper pairs a Max 2-SAT hardness reduction with an algorithm based on a reduction to 2-SAT. The four-rank hardness construction uses a polynomial-time reduction from Monotone 3-SAT. A reduction translates instances of one decision problem into another so that a complexity conclusion carries across.
The authors describe the pattern as a complexity jump from two to three ranks and another from three to four. They offer an intuitive correspondence between zero-agony k-rank cases and (k − 1)-SAT. That framing helps explain why the rank count is central, but it is presented as an interpretation of the results rather than as a claim that every temporal-graph instance is literally a SAT formula.
A map, not a benchmark
The scope of the evidence is formal by design. The study examines temporal digraph decision instances and constructed reductions, with complexity classifications and running-time bounds as its main outputs; it does not evaluate hierarchy quality or algorithm performance on real-world network data.
Several boundaries remain unsettled in the supplied analysis. It reports XP for n when n is used alone, rather than FPT; XP in α for the three-rank, one-change-point case, rather than FPT; and leaves behavior beyond one change point as a research direction. It also says that NP-hardness for the three-rank case on an underlying DAG is unclear.
The document identifies itself as arXiv:2608.20077v1 [cs.DS], dated 20 Aug 2026. It reports support from DFG Research Training Group 2434, “Facets of Complexity”, and no journal venue is reported in the supplied metadata.
Paper data and sources
Original title: Parameterized Complexity of Temporal Agony
Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text