2026-07-25T01:58:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24562 2026-03-16T08:09:59Z ddc:004 open_access

Recognizing and Realizing Temporal Reachability Graphs Erlebach, Thomas Michail, Othon Morawietz, Nils parameterized complexity temporal graphs FPT algorithm feedback edge set directed graph recognition A temporal graph 𝒢 = (G,λ) can be represented by an underlying graph G = (V,E) together with a function λ that assigns to each edge e ∈ E the set of time steps during which e is present. The reachability graph of 𝒢 is the directed graph D = (V,A) with (u,v) ∈ A if and only if there is a temporal path from u to v. We study the Reachability Graph Realizability (RGR) problem that asks whether a given directed graph D = (V,A) is the reachability graph of some temporal graph. The question can be asked for undirected or directed temporal graphs, for reachability defined via strict or non-strict temporal paths, and with or without restrictions on λ (simple, proper, or both). Answering an open question posed by Casteigts et al. (TCS 2024), we show that all variants of the problem are NP-complete, except for two variants that become trivial in the directed case. For undirected temporal graphs, we consider the complexity of the problem with respect to the solid graph, that is, the graph containing all edges that could potentially receive a label in any realization. We show that the RGR problem is fixed-parameter tractable for the feedback edge set number of the solid graph. As we show, the latter parameter can presumably not be replaced by smaller parameters like feedback vertex set number or treedepth, since the problem is W[2]-hard for them. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Erlebach and Othon Michail and Nils Morawietz 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.93 urn:nbn:de:0030-drops-245627 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.93 eng https://creativecommons.org/licenses/by/4.0/legalcode