RECORD
Parameterized Complexity of Temporal Agony
Data Structures and Algorithms · Submitted 20 Aug 2026
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $\alpha$, and NP-hard for $k=4$ and $\ell=1$ even for $\alpha=0$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $\alpha$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $\alpha$, and NP-hard for $k=4$ and $\ell=1$ even for $\alpha=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. | background 1.00 | 0.05 | 0.01 | asserted 0.78 |
| s1 | In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s2 | Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. | background 0.84 | 0.07 | 0.02 | asserted 1.00 |
| s3 | Backward arcs are penalized depending on the difference between the corresponding ranks. | background 0.81 | 0.08 | 0.02 | asserted 1.00 |
| s4 | Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $\alpha$ (called temporal agony). | background 0.84 | 0.13 | 0.03 | asserted 0.79 |
| s5 | We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. | contribution 1.00 | 0.86 | 0.10 | asserted 0.86 |
| s6 | We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $\alpha$, and NP-hard for $k=4$ and $\ell=1$ even for $\alpha=0$. | result 0.99 | 0.96 | 0.76 | asserted 1.00 |
| s7 | We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$. | result 0.91 | 0.97 | 0.17 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $\alpha$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $\alpha$, and NP-hard for $k=4$ and $\ell=1$ even for $\alpha=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.