Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Temporal Graph Realization With Bounded Stretch

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read Assigning periodic time-labels so that fastest temporal paths respect static distances is NP-hard to approximate, but a simple radial labeling keeps the stretch below $\Delta$.

desk verdict Solid new problem and hardness results; Section 7's XP local-search proof has a fixable but real gap. read the letter →

arxiv 2504.14258 v1 pith:NYEDX737 submitted 2025-04-19 cs.DS cs.DM

George B. Mertzios , Hendrik Molter , Nils Morawietz , Paul G. Spirakis This is my paper · ORCID
classification cs.DScs.DM MSC 68Q1768Q2568R10
keywords periodictemporalgraphslabelingstretchfastestpathgraphrealizationNP-hardnessapproximationalgorithmlocalsearch
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 introduces and analyzes the problem of assigning one periodic time-label from $\{1,\dots,\Delta\}$ to every edge of a static graph so that, in the resulting $\Delta$-periodic temporal graph, the duration of the fastest temporal path between any two vertices is at most $\alpha$ times their distance in the static graph. The paper establishes that this task, called Stretched Temporal Graph Realization (STGR), is NP-hard to approximate within a factor of $\Delta^{1-\varepsilon}$ for any $0<\varepsilon<1$ and within a factor of $2^{n^c}$ for any $c>1$, unless P equals NP. On the positive side, it gives a polynomial-time radius algorithm that labels any graph with stretch at most $\Delta - \frac{\Delta-1}{\min(\mathrm{rad}+1,\mathrm{diam})}$, which is strictly below the trivial bound $\Delta$, and it shows this guarantee is tight on some NP-hard instances. The paper also proves NP-hardness for constant period length and constant stretch, including $\Delta=3$, $\alpha=1$, diameter 2, gives fixed-parameter algorithms via monadic second-order logic, and analyzes a local-search variant that is W[2]-hard but in XP when parameterized by the number of labels changed.

What carries the argument

The load-bearing object is the periodic labeling $\lambda:E\to\{1,\dots,\Delta\}$ together with the induced waiting time: when a temporal path uses two consecutive edges with labels $a$ and $b$, the wait at the shared vertex is $b-a$ if $b>a$, $\Delta+b-a$ if $b<a$, and $\Delta$ if $b=a$; the stretch is the maximum over vertex pairs of the ratio of fastest-path duration to static distance. The main constructive mechanism is the radius algorithm, which fixes a vertex whose eccentricity equals the graph's radius and labels every edge between layer $i-1$ and layer $i$ with $\lceil \Delta/2\rceil$ for odd $i$ and with $\Delta$ for even $i$; alternating these two labels controls the worst-case wait at the center and yields the bound $\Delta - \frac{\Delta-1}{\min(\mathrm{rad}+1,\mathrm{diam})}$. On the hardness side, the mechanisms are gap reductions from the gossip problem and from 3-coloring, using sunglasses gadgets that force certain edge pairs to carry distinct labels. For the fixed-parameter results, the mechanism is a monadic second-order formulation of the stretch condition, with cardinality extensions that make the problem expressible in the fragments covered by the relevant model-checking meta-theorems.

What would settle it

The most directly checkable point is the local-search XP proof: exhaustively enumerate all Fixed Edges Relabel STGR instances with one changed edge and compare the Section 7 midpoint binary search against brute force. A single instance with a feasible labeling that the binary search misses would invalidate the algorithm as written; if no such instance exists, the missing proof can likely be supplied.

Watch

Extended reading notes

Core claim

The central claim is that keeping the multiplicative stretch of a periodic temporal labeling close to the static distances is computationally hard, yet a simple constructive labeling can always beat the trivial worst case. For every $0<\varepsilon<1$ and every $c>1$, STGR has no polynomial-time $\Delta^{1-\varepsilon}$-approximation and no polynomial-time $2^{n^c}$-approximation unless P equals NP; the proof is a gap reduction from the gossip problem, where a yes-instance admits a labeling whose stretch is independent of $\Delta$, while a no-instance forces some fastest temporal path to cross a period boundary, making the stretch grow with $\Delta$. Complementing this, the radius algorithm picks a vertex of minimum eccentricity and labels edges between consecutive distance layers alternately with $\lceil \Delta/2\rceil$ and $\Delta$; the paper proves this produces stretch at most $\Delta - \frac{\Delta-1}{\min(\mathrm{rad}+1,\mathrm{diam})}$, and on trees it gives stretch at most $\frac{\Delta+1}{2}$, which is optimal when the maximum degree is at least $\Delta+1$ and a 2-approximation on general trees. The decision version is NP-hard even for $\Delta=3$, $\alpha=1$, and diameter 2, resolving an open question from earlier work, and remains NP-hard for every constant $\Delta\ge 3$ and every constant $\alpha\ge 1$.

Load-bearing premise

The claim that the local-search variant can be solved in polynomial time for any constant number of changed labels depends on the unproven assumption that, after fixing the other labels and the relative order of labels, a simple midpoint binary search over one changed edge's allowed label range finds a feasible label whenever one exists; the paper does not show the feasible label set has the interval structure this search would need.

Editorial extensions

If this is right

  • Unless P equals NP, no polynomial-time algorithm can guarantee stretch below $\Delta^{1-\varepsilon}$ or $2^{n^c}$, so the trivial $\Delta$ bound is qualitatively hard to improve in the worst case.
  • The radius algorithm runs in polynomial time and always returns a labeling with stretch at most $\Delta - \frac{\Delta-1}{\min(\mathrm{rad}+1,\mathrm{diam})}$, which is strictly better than $\Delta$ whenever the radius and diameter are small.
  • On trees the radius algorithm achieves stretch at most $\frac{\Delta+1}{2}$; on trees with maximum degree at least $\Delta+1$ this is exactly optimal, and on general trees it is a 2-approximation.
  • STGR is NP-hard even for $\Delta=3$, $\alpha=1$, and diameter 2, so the easy-looking small cases are already intractable; hardness also holds for every constant $\Delta\ge 3$ and every constant $\alpha\ge 1$.
  • The problem is fixed-parameter tractable with respect to neighborhood diversity plus $\Delta$ and with respect to treewidth plus diameter plus $\Delta$, while the local-search variant that changes at most $k$ labels is in XP and W[2]-hard with respect to $k$.

Reading between the lines

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

  • Beyond the paper: the radius algorithm's two-label alternation suggests a testable design heuristic—layered periodic schedules that interleave $\lceil \Delta/2\rceil$ and $\Delta$ along BFS layers—which could be extended to directed graphs, weighted graphs, or aperiodic schedules and checked for analogous worst-case wait bounds.
  • Beyond the paper: the hardness cluster around $\alpha=\Delta/2$ indicates a possible phase transition in the stretch parameter; for $\alpha$ just below $\Delta/2$ the problem is NP-hard for every $\Delta$, and deciding what happens for larger $\alpha$ is a natural next step.
  • Beyond the paper: if the binary-search gap in the local-search XP algorithm is repaired, the algorithm would provide a practical improvement heuristic—start from any labeling and reduce stretch by changing a constant number of labels in polynomial time—since the W[2]-hardness only rules out FPT-style exact local improvement.
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

2 major / 5 minor

Summary. The paper introduces Stretched Temporal Graph Realization (STGR): given an undirected graph G, a period Delta, and a rational alpha >= 1, decide whether each edge can receive one label in {1,...,Delta} so that in the resulting Delta-periodic temporal graph, the duration of a fastest temporal path between every ordered pair (u,v) is at most alpha times the static distance in G. The contributions are: (1) inapproximability results ruling out polynomial-time Delta^{1-epsilon}- and 2^{n^c}-approximations under P != NP; (2) a polynomial-time 'radius algorithm' with stretch at most Delta - (Delta-1)/min(rad+1,diam), plus improved guarantees on trees and a 2-approximation for general trees; (3) NP-hardness for Delta=3 and alpha in [1,1.5) on diameter-2 graphs (answering an open question), for Delta=3 and alpha in [1.5,2), and for all constant Delta >= 3 and all constant alpha >= 1; (4) fixed-parameter tractability via MSO_lin and CMSO encodings parameterized by neighborhood diversity plus Delta, and by treewidth plus diameter plus Delta; and (5) a local-search variant LS STGR claimed to admit an XP algorithm for the parameter k and to be W[2]-hard. The XP algorithm for Fixed Edges Relabel STGR is the part I cannot verify as written.

Significance. The problem is natural and well motivated, and the paper is largely self-contained: the reductions use 3-Coloring, the gossip problem, and Hitting Set, while the authors' earlier arbitrary-bound problem [38] appears only as motivation, so there is no evident circularity. The MSO encodings in Section 6 are explicit and checkable, and the radius algorithm gives a clean, falsifiable approximation guarantee. The hardness results for small Delta and constant alpha, if correct, are valuable and answer a posed open question. The main weakness is that one central algorithmic claim, the XP algorithm for LS STGR in Theorem 7.1, rests on an unjustified binary-search step, and there is also an inconsistency in the construction used in Lemma 5.1. If these two technical points are repaired, the paper would be a solid contribution to temporal graph realization; in its current form, it requires major revision.

major comments (2)
  1. [Section 7, Theorem 7.1 (paragraph beginning 'Our algorithm proceeds as follows')] The binary-search step is not justified. After fixing a zone allocation and a time-label profile, the algorithm claims to search each edge e_i in F independently and to find a feasible label whenever one exists. For a single edge with all other labels fixed, the set of labels satisfying a fixed pair (s,t) is a union of sets of the form {x : x <= a}, {x : x >= b}, or the whole interval, because a path using e_i either has it first, last, or internal. Since the condition for a pair is existential over temporal paths, the feasible set for that pair is a union of such prefix/suffix sets, and the intersection over all pairs can be two separated intervals. A midpoint binary search that discards one half can therefore miss a nonempty feasible set. The text neither computes interval endpoints nor proves any monotonicity property of the feasibility predicate. Furthermore, the independence of the searches is unsupported: changing the label of e_i changes the constants in the duration expressions for paths that also use e_j, so coordinate-wise binary searches need not converge to a joint feasible labeling. Since the XP bound of Theorem 7.1 rests entirely on this step, the local-search result is unproven as written.
  2. [Section 5.1, Lemma 5.1 (construction of G' and proof)] The construction adds a vertex c* and makes {c*} union (V'\V) into a clique. Since V'\V consists of the center c and the added x-vertices (plus c* itself), this does not make c* adjacent to any vertex of the original set V. Nevertheless, the proof repeatedly uses (u,c*,v) as a length-2 path for u,v in V: the forward direction uses (b,c*,a) when {a,b} is an edge of G, and the reverse direction asserts that (u,c,v) and (u,c*,v) are the only u-v paths of length less than 3. These claims are false under the stated construction. The accompanying sentence that 'both vertices c and c* are adjacent to all vertices' is inconsistent with the formal construction. If the intended construction is to make c* universal (in particular adjacent to all vertices of V), the proof may go through, but the text must be corrected explicitly; as written, the reduction and hence the claimed NP-hardness for Delta=3 and alpha in [1,1.5) are invalid.
minor comments (5)
  1. [Section 4, Lemma 4.5] The clause 'if l1 != l2 then the durations ... are both Delta+1, while both these durations are strictly less than Delta+1 if l1 != l2' is contradictory; the first condition should be l1 = l2. Also, for odd Delta the minimized maximum duration is (Delta+3)/2 rather than (Delta+2)/2; the stated lower bound remains valid, but the algebra should be corrected.
  2. [Section 4, Lemma 4.2] In the line 'alpha_rad = Delta - (Delta-1)/rad >= max{alpha_l = Delta - (Delta-1)/rad | l in [2,rad]}', the expression on the right should be Delta - (Delta-1)/l.
  3. [Section 5.2, Definition 5.8] The definition says 'Let Delta be an odd integer with Delta >= 4', but Definition 5.8 is for even Delta; this should read 'even integer'.
  4. [Section 6, proof of Lemma 6.5] In the paragraph explaining how the partition X_1,...,X_Delta is chosen, the text says 'If the waiting time at vertex x is i, we put x in X_{i+1}'; this should be X_i, since the formula uses X_i for waiting time i.
  5. [Section 5.1, Lemma 5.1 proof] The phrase 'consecutive lime labels' should be 'consecutive time labels'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: STGR’s hardness, approximation, and FPT results rest on external benchmarks and self-contained arguments, not on fitted inputs or load-bearing self-citations.

full rationale

The paper does not reduce any claimed result to its own inputs by construction. STGR is introduced as a special case of the authors' earlier arbitrary-bound problem [38], and the text says so explicitly, but that earlier work is used only as motivation and context; the new NP-hardness and inapproximability proofs are gap reductions from the gossip problem and from 3-Coloring, the radius algorithm's stretch guarantees are proven directly from the labeling it produces, and the FPT results are MSO-expressibility arguments combined with Courcelle-type metatheorems from the literature. The Section 7 XP algorithm for Local Search STGR relies on a binary search over labels whose correctness is not fully justified in the paper, but that is an unproven algorithmic step and a correctness risk, not a case where a prediction is forced by construction or by self-citation; it also does not import an unverified result from the authors' prior work. Self-citations such as [38] and [32] are contextual and are not load-bearing for the new theorems. Thus no circular step that can be exhibited by quote-and-reduction is present.

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

No free parameters are fitted. The sunglasses gadgets are proof constructions, not postulated empirical entities, so they are not listed as invented entities. The paper's load-bearing assumptions are standard complexity hypotheses, external NP-hardness results, MSO metatheorems, and the periodic temporal graph semantics.

assumptions (6)
  • domain assumption P != NP
    All NP-hardness and inapproximability claims are conditional on this standard conjecture.
  • standard math 3-Coloring is NP-hard (Karp 1972)
    Used as source of reductions in Section 5.
  • standard math Gossip problem is NP-hard (Goebel et al. 1991)
    Used as source of gap reduction in Section 3.
  • standard math Hitting Set is W[2]-hard
    Used for local search hardness in Section 7.
  • standard math MSO model checking meta-theorems of Courcelle and Knop et al. are correct
    Basis for FPT results in Section 6.
  • domain assumption Periodic temporal graph model: each edge is active exactly once per period at its label
    The problem definition under study; conclusions apply to this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Temporal Graph Realization With Bounded Stretch." pith.science (2026). https://pith.science/paper/NYEDX737

@misc{pith2026250414258,
  author       = {Pith},
  title        = {Pith review of: Temporal Graph Realization With Bounded Stretch},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NYEDX737}},
  note         = {Machine review of arXiv:2504.14258}
}
abstract

A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first $\Delta$ time steps, and then it reappears recurrently every $\Delta$ time steps, where $\Delta$ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are `stretched', compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph $G$, the task is to assign to each edge one time-label between 1 and $\Delta$ such that, in the resulting periodic temporal graph with period~$\Delta$, the duration of the fastest temporal path from any vertex $u$ to any other vertex $v$ is at most $\alpha$ times the distance between $u$ and $v$ in $G$. Here, the value of $\alpha$ measures how much the shortest paths are allowed to be \emph{stretched} once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the \textit{radius-algorithm}) which always guarantees an approximation strictly smaller than $\Delta$, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most $k$ edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to $k$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Exploring Temporal Graphs with Frequent and Regular Edges

    cs.DS 2025-05 reject novelty 6.0 of 10

    A temporal graph in which every edge appears at least once every F timesteps can be explored in F(2n-3) steps, and this is tight up to an additive constant.

Reference graph

Works this paper leans on

44 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [2]

    Using petal-decompositions to build a low stretch spanning tree

    Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. SIAM J. Comput. , 48(2):227--248, 2019

    2019

  2. [38]

    Mertzios, Hendrik Molter, Nils Morawietz, and Paul G

    George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Realizing temporal transportation trees. In Proceedings of the 51st Workshop on Graph-Theoretic Concepts in Computer Science ( WG ) , LNCS. Springer, 2025. To appear. Full version: https://arxiv.org/abs/2403.18513

    arXiv 2025

  3. [1]

    Nearly tight low stretch spanning trees

    Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly tight low stretch spanning trees. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 781--790. IEEE Computer Society, 2008

    work page 2008

  4. [3]

    Mertzios, and Paul G Spirakis

    Eleni C Akrida, Leszek G a sieniec, George B. Mertzios, and Paul G Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems , 61:907--944, 2017

    work page 2017

  5. [4]

    Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs

    Emmanuel Arrighi, Niels Gr \"u ttemeier, Nils Morawietz, Frank Sommer, and Petra Wolf. Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs. In Proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , pages 283--297, 2023

    work page 2023

  6. [5]

    Sparse temporal spanners with low stretch

    Davide Bil \` o , Gianlorenzo D'Angelo, Luciano Gual \` a , Stefano Leucci, and Mirko Rossi. Sparse temporal spanners with low stretch. In Proceedings of the 30th Annual European Symposium on Algorithms ( ESA ) , volume 244 of LIPIcs , pages 19:1--19:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

    work page 2022

  7. [6]

    On the realization of a (p, s) -digraph with prescribed degrees

    Wai-Kai Chen. On the realization of a (p, s) -digraph with prescribed degrees. Journal of the Franklin Institute , 281(5):406--422, 1966

    work page 1966

  8. [7]

    Fast algorithms for constructing t-spanners and paths with stretch t

    Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. , 28(1):210--236, 1998

    work page 1998

Show all 44 references
  1. [8]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I . R ecognizable sets of finite graphs. Information and computation , 85(1):12--75, 1990

    1990

  2. [9]

    Graph structure and monadic second-order logic: a language-theoretic approach , volume 138

    Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach , volume 138. Cambridge University Press, 2012

    2012

  3. [10]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

    2015

  4. [11]

    Copnumbers of periodic graphs

    Jean - Lou De Carufel , Paola Flocchini, Nicola Santoro, and Fr \' e d \' e ric Simard. Copnumbers of periodic graphs. CoRR , abs/2310.13616, 2023

    2023 arXiv

  5. [12]

    Cops & robber on periodic temporal graphs: Characterization and improved bounds

    Jean - Lou De Carufel , Paola Flocchini, Nicola Santoro, and Fr \' e d \' e ric Simard. Cops & robber on periodic temporal graphs: Characterization and improved bounds. In Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti, editors, Structural Information a...

    2023

  6. [13]

    Optimizing reachability sets in temporal graphs by delaying

    Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. Information and Computation , 285:104890, 2022

    2022

  7. [14]

    Graph Theory, 5th Edition , volume 173 of Graduate Texts in Mathematics

    Reinhard Diestel. Graph Theory, 5th Edition , volume 173 of Graduate Texts in Mathematics . Springer, 2016

    2016

  8. [15]

    Spielman, and Shang - Hua Teng

    Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang - Hua Teng. Lower-stretch spanning trees. SIAM J. Comput. , 38(2):608--628, 2008

    2008

  9. [16]

    Approximating minimum max-stretch spanning trees on unweighted graphs

    Yuval Emek and David Peleg. Approximating minimum max-stretch spanning trees on unweighted graphs. SIAM J. Comput. , 38(5):1761--1781, 2008

    2008

  10. [17]

    Mertzios, and Viktor Zamaraev

    Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences , 119:60--77, 2021

    2021

  11. [18]

    Assigning times to minimise reachability in temporal graphs

    Jessica Enright, Kitty Meeks, and Fiona Skerman. Assigning times to minimise reachability in temporal graphs. Journal of Computer and System Sciences , 115:169--186, 2021

    2021

  12. [19]

    Graphs with prescribed degrees of vertices

    Paul Erd \"o s and Tibor Gallai. Graphs with prescribed degrees of vertices. Mat. Lapok , 11:264--274, 1960

    1960

  13. [20]

    Recognizing and Realizing Temporal Reachability Graphs , 2025

    Thomas Erlebach, Othon Michail, and Nils Morawietz. Recognizing and Realizing Temporal Reachability Graphs , 2025. arXiv:2503.15771 [cs]

    2025 arXiv

  14. [21]

    Spooner, and Petra Wolf

    Thomas Erlebach, Nils Morawietz, Jakob T. Spooner, and Petra Wolf. A cop and robber game on edge-periodic temporal graphs. Journal of Computer and System Sciences , 144:103534, 2024

    2024

  15. [22]

    Parameterized algorithms for multi-label periodic temporal graph realization

    Thomas Erlebach, Nils Morawietz, and Petra Wolf. Parameterized algorithms for multi-label periodic temporal graph realization. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks ( SAND ) , volume 292 of LIPIcs , pages 12:1--12:16. Schloss Dagstu...

    2024

  16. [23]

    Fellows, Fedor V

    Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, and Yngve Villanger. Local search: Is brute-force avoidable? Journal of Computer and System Sciences , 78 ( 3 ): 707--719 , 2012

    2012

  17. [24]

    Temporal graph classes: A view through temporal separators

    Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science , 806:197--218, 2020

    2020

  18. [25]

    Label-connected graphs and the gossip problem

    Frits G \"o bel, J Orestes Cerdeira, and Hendrik Jan Veldman. Label-connected graphs and the gossip problem. Discrete Mathematics , 87(1):29--40, 1991

    1991

  19. [26]

    Local search for string problems: Brute-force is essentially optimal

    Jiong Guo, Danny Hermelin, and Christian Komusiewicz. Local search for string problems: Brute-force is essentially optimal . Theoretical Computer Science , 525 : 30--41 , 2014

    2014

  20. [27]

    Louis Hakimi

    S. Louis Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. I . Journal of the Society for Industrial and Applied Mathematics , 10(3):496--506, 1962

    1962

  21. [28]

    Louis Hakimi and Stephen S

    S. Louis Hakimi and Stephen S. Yau. Distance matrix of a graph and its realizability. Quarterly of applied mathematics , 22(4):305--317, 1965

    1965

  22. [29]

    Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations ( P roc. S ympos., IBM T homas J . W atson R es. C enter, Y orktown H eights, N . Y ., 1972) , pages 85--103. Plenum, New York, 1972

    1972

  23. [30]

    Kleinberg, and Amit Kumar

    David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences , 64(4):820--842, 2002

    2002

  24. [31]

    Mertzios, Hendrik Molter, and Paul G

    Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. J. Comput. Syst. Sci. , 146:103564, 2024

    2024

  25. [32]

    Mertzios, Hendrik Molter, and Paul G

    Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. Temporal graph realization from fastest paths. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks ( SAND ) , volume 292 of LIPIcs , pages 16:1--16:18. Schloss Dagstuhl - Leib...

    2024

  26. [33]

    Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity

    Dusan Knop, Martin Kouteck \' y , Tom \' a s Masar \' k, and Tom \' a s Toufar. Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. , 15(4), 2019

    2019

  27. [34]

    Algorithmic meta-theorems for restrictions of treewidth

    Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64:19--37, 2012

    2012

  28. [35]

    Searching the k -change neighborhood for TSP is W [1]-hard

    D \' a niel Marx. Searching the k -change neighborhood for TSP is W [1]-hard . Operations Research Letters , 36 ( 1 ): 31--36 , 2008

    2008

  29. [36]

    Reducing reachability in temporal graphs: Towards a more realistic model of real-world spreading processes

    Kitty Meeks. Reducing reachability in temporal graphs: Towards a more realistic model of real-world spreading processes. In Proceedings of the 18th Conference on Computability in Europe (CiE) , volume 13359 of Lecture Notes in Computer Science , pages 186--195. Springer, 2022

    2022

  30. [37]

    Mertzios, Othon Michail, and Paul G

    George B. Mertzios, Othon Michail, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica , 81(4):1416--1449, 2019

    2019

  31. [39]

    Directed temporal tree realization for periodic public transport: Easy and hard cases, 2025

    Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Directed temporal tree realization for periodic public transport: Easy and hard cases, 2025

    2025

  32. [40]

    Temporal reachability minimization: Delaying vs

    Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal reachability minimization: Delaying vs. deleting. J. Comput. Syst. Sci. , 144:103549, 2024

    2024

  33. [41]

    On the complexity of local search problems with scalable neighborhoods

    Nils Morawietz. On the complexity of local search problems with scalable neighborhoods . PhD thesis, 2024. Dissertation, Friedrich-Schiller-Universit \"a t Jena

    2024

  34. [42]

    A timecop's work is harder than you think

    Nils Morawietz, Carolin Rehs, and Mathias Weller. A timecop's work is harder than you think. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS) , volume 170, pages 71:1--71:14, 2020

    2020

  35. [43]

    A timecop's chase around the table

    Nils Morawietz and Petra Wolf. A timecop's chase around the table. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS) , pages 77:1--77:18, 2021

    2021

  36. [44]

    The complexity of finding separators in temporal graphs

    Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The complexity of finding separators in temporal graphs. Journal of Computer and System Sciences , 107:72--92, 2020

    2020

Pith tools

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