34 Search Results for "Wolf, Petra"

Document
DOI: 10.4230/LIPIcs.STACS.2026.24
Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics

Authors: Justine Cauvi, Nils Morawietz, and Laurent Viennot

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.
Cite as

Justine Cauvi, Nils Morawietz, and Laurent Viennot. Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:LIPIcs.STACS.2026.24,
  author =	{Cauvi, Justine and Morawietz, Nils and Viennot, Laurent},
  title =	{{Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.24},
  URN =		{urn:nbn:de:0030-drops-255139},
  doi =		{10.4230/LIPIcs.STACS.2026.24},
  annote =	{Keywords: network design, temporal paths, foremost paths, fastest paths, shortest paths, non-strict paths, periodic temporal graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.12
Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set

Authors: Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
A temporal graph is a finite sequence of graphs, called snapshots, over the same vertex set. Many temporal graph problems turn out to be much more difficult than their static counterparts. One such problem is Timeline Vertex Cover (also known as MinTimeline_∞), a temporal analogue to the classical Vertex Cover problem. In this problem, one is given a temporal graph 𝒢 and two integers k and 𝓁, and the goal is to cover each edge of each snapshot by selecting for each vertex at most k activity intervals of length at most 𝓁 each. Here, an edge uv in the ith snapshot is covered, if an activity interval of u or v is active at time i. In this work, we continue the algorithmic study of Timeline Vertex Cover and introduce the Timeline Dominating Set problem where we want to dominate all vertices in each snapshot by the selected activity intervals. We analyze both problems from a classical and parameterized point of view and also consider partial problem versions, where the goal is to cover (dominate) at least t edges (vertices) of the snapshots. With respect to the parameterized complexity, we consider the temporal graph parameters vertex-interval-membership-width (vimw) and interval-membership-width (imw). We show that all considered problems admit FPT-algorithms when parameterized by vimw+k+𝓁. This provides a smaller parameter combination than the ones used for previously known FPT-algorithms for Timeline Vertex Cover. Surprisingly, for imw+k+𝓁, Timeline Dominating Set turns out to be easier than Timeline Vertex Cover, by also admitting an FPT-algorithm, whereas the vertex cover version is NP-hard even if imw+k+𝓁 is constant. We also consider parameterization by combinations of n, the vertex set size, with k or 𝓁 and parameterization by t. Here, we show for example that both partial problems are fixed-parameter tractable for t which significantly improves and generalizes a previous result for a special case of Partial Timeline Vertex Cover with k = 1.
Cite as

Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{herrmann_et_al:LIPIcs.IPEC.2025.12,
  author =	{Herrmann, Anton and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.12},
  URN =		{urn:nbn:de:0030-drops-251446},
  doi =		{10.4230/LIPIcs.IPEC.2025.12},
  annote =	{Keywords: NP-hard problem, FPT-algorithm, interval-membership-width, Color coding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.17
Realization of Temporally Connected Graphs Based on Degree Sequences

Authors: Arnaud Casteigts, Michelle Döring, and Nils Morawietz

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in 𝒪(n) time for graphical degree sequences (realized as simple temporal graphs) and in 𝒪(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive 𝒪(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence 𝐝, a temporally connected graph whose underlying (multi)graph is a realization of 𝐝, if one exists.
Cite as

Arnaud Casteigts, Michelle Döring, and Nils Morawietz. Realization of Temporally Connected Graphs Based on Degree Sequences. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.ISAAC.2025.17,
  author =	{Casteigts, Arnaud and D\"{o}ring, Michelle and Morawietz, Nils},
  title =	{{Realization of Temporally Connected Graphs Based on Degree Sequences}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.17},
  URN =		{urn:nbn:de:0030-drops-249256},
  doi =		{10.4230/LIPIcs.ISAAC.2025.17},
  annote =	{Keywords: temporal paths, gossiping, (multi)graphical degree sequences, edge-disjoint spanning trees, linear time algorithms}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.17
Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.4
Heuristics for Exact 1-Planarity Testing

Authors: Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.
Cite as

Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2025.4,
  author =	{Fink, Simon D. and M\"{u}nch, Miriam and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Heuristics for Exact 1-Planarity Testing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.4},
  URN =		{urn:nbn:de:0030-drops-249909},
  doi =		{10.4230/LIPIcs.GD.2025.4},
  annote =	{Keywords: 1-Planarity, Experiments, Backtracking}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.32
Planar Stories of Graph Drawings: Algorithms and Experiments

Authors: Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.
Cite as

Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf. Planar Stories of Graph Drawings: Algorithms and Experiments. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.GD.2025.32,
  author =	{Binucci, Carla and Cornelsen, Sabine and Didimo, Walter and Hong, Seok-Hee and Katsanou, Eleni and Patrignani, Maurizio and Symvonis, Antonios and Wolf, Samuel},
  title =	{{Planar Stories of Graph Drawings: Algorithms and Experiments}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.32},
  URN =		{urn:nbn:de:0030-drops-250182},
  doi =		{10.4230/LIPIcs.GD.2025.32},
  annote =	{Keywords: Graph Drawing, Dynamic Graphs, Graph Stories, Heuristics, ILP}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.3
Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

Authors: Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We study the complexity of the directed periodic temporal graph realization problem. This work is motivated by the design of periodic schedules in public transport with constraints on the quality of service. Namely, we require that the fastest path between (important) pairs of vertices is upper bounded by a specified maximum duration, encoded in an upper distance matrix D. While previous work has considered the undirected version of the problem, the application in public transport schedule design requires the flexibility to assign different departure times to the two directions of an edge. A problem instance can only be feasible if all values of the distance matrix are at least shortest path distances. However, the task of realizing exact fastest path distances in a periodic temporal graph is often too restrictive. Therefore, we introduce a minimum slack parameter k that describes a lower bound on the maximum allowed waiting time on each path. We concentrate on tree topologies and provide a full characterization of the complexity landscape with respect to the period Δ and the minimum slack parameter k, showing a sharp threshold between NP-complete cases and cases which are always realizable. We also provide hardness results for the special case of period Δ = 2 for general directed and undirected graphs.
Cite as

Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:OASIcs.ATMOS.2025.3,
  author =	{Meusel, Julia and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{3:1--3:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.3},
  URN =		{urn:nbn:de:0030-drops-247594},
  doi =		{10.4230/OASIcs.ATMOS.2025.3},
  annote =	{Keywords: Periodic timetabling, service quality, temporal graph, graph realization, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.4
Visualization of Event Graphs for Train Schedules

Authors: Johann Hartleb, Marie Schmidt, Samuel Wolf, and Alexander Wolff

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
Train timetables can be represented as event graphs, where events correspond to a train passing through a location at a certain point in time. A visual representation of an event graph is important for many applications such as dispatching and (the development of) dispatching software. A common way to represent event graphs are time-space diagrams. In such a diagram, key locations are visualized on the y-axis and time on the x-axis of a coordinate system. A train’s movement is then represented as a connected sequence of line segments in this coordinate system. This visualization allows for an easy detection of infrastructure conflicts and safety distance violations. However, time-space diagrams are usually used only to depict event graphs that are restricted to corridors, where an obvious ordering of the locations exists. In this paper, we consider the visualization of general event graphs in time-space diagrams, where the challenge is to find an ordering of the locations that produces readable drawings. We argue that this means to minimize the number of turns, i.e., the total number of changes in y-direction. To this end, we establish a connection between this problem and Maximum Betweenness. Then we develop a preprocessing strategy to reduce the instance size. We also propose a parameterized algorithm and integer linear programming formulations. We experimentally evaluate the preprocessing strategy and the integer programming formulations on a real-world dataset. Our best algorithm solves every instance in the dataset in less than a second. This suggests that turn-optimal time-space diagrams can be computed in real time.
Cite as

Johann Hartleb, Marie Schmidt, Samuel Wolf, and Alexander Wolff. Visualization of Event Graphs for Train Schedules. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartleb_et_al:OASIcs.ATMOS.2025.4,
  author =	{Hartleb, Johann and Schmidt, Marie and Wolf, Samuel and Wolff, Alexander},
  title =	{{Visualization of Event Graphs for Train Schedules}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{4:1--4:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.4},
  URN =		{urn:nbn:de:0030-drops-247607},
  doi =		{10.4230/OASIcs.ATMOS.2025.4},
  annote =	{Keywords: Graph Drawing, Event Graphs, Integer Linear Programming, Parameterized Algorithms, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.93
Recognizing and Realizing Temporal Reachability Graphs

Authors: Thomas Erlebach, Othon Michail, and Nils Morawietz

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
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.
Cite as

Thomas Erlebach, Othon Michail, and Nils Morawietz. Recognizing and Realizing Temporal Reachability Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 93:1-93:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ESA.2025.93,
  author =	{Erlebach, Thomas and Michail, Othon and Morawietz, Nils},
  title =	{{Recognizing and Realizing Temporal Reachability Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{93:1--93:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.93},
  URN =		{urn:nbn:de:0030-drops-245627},
  doi =		{10.4230/LIPIcs.ESA.2025.93},
  annote =	{Keywords: parameterized complexity, temporal graphs, FPT algorithm, feedback edge set, directed graph recognition}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.26
Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks

Authors: David Andrew Green

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
The Artemis programme seeks to develop and test concepts, hardware and approaches to support long term habitation of the Lunar surface, and future missions to Mars. In preparation for the Artemis missions determination of tasks to be performed, the functional requirements of such tasks and as mission duration extends whether physiological deconditioning becomes functionally significant, compromising the crew member’s ability to perform critical tasks on the surface, and/or upon return to earth [MoLo-LUNA – leveraging the Molo programme (and several other activities) - could become a key supporting activity for LUNA incl. validation of the Puppeteer offloading system itself via creation of a complementary MoLo-LUNA-LAB. Furthermore, the MoLo-LUNA programme could become a key facilitator of simulator suit instrumentation/definition, broader astronaut training activities and mission architecture development – including Artemis mission simulations. By employing a Puppeteer system external to the LUNA chamber hall it will optimise utilisation and cost-effectiveness of LUNA, and as such represents a critical service to future LUNA stakeholders. Furthermore, MoLo-LUNA would generate a unique data set that can be leveraged to predict de-conditioning on the Lunar surface - and thereby optimise functionality, and minimise mission risk – including informing the need for, and prescription of exercise countermeasures on the Lunar Surface and in transit. Thus, MoLo-LUNA offers a unique opportunity to place LUNA, and ESA as a key ongoing provider of evidence to define, optimise and support crew Artemis surface missions.
Cite as

David Andrew Green. Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{green:OASIcs.SpaceCHI.2025.26,
  author =	{Green, David Andrew},
  title =	{{Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{26:1--26:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.26},
  URN =		{urn:nbn:de:0030-drops-240166},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.26},
  annote =	{Keywords: Locomotion, hypogravity, modelling, Lunar}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.31
Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis

Authors: Niels Grüttemeier and Klaus Heeger

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider the problem of repairing production schedules in a job-shop setting by reducing pre-planned waiting times. Herein, a schedule of all jobs is given. To compensate unforeseen disturbances, this schedule contains waiting times between the execution of two consecutive tasks of a job. Further, we assume that the schedule temporarily overloads some machines, e.g. due to reduced machine capacities because of worker sickness or (partially) broken machines. We study the problem of removing as few waiting times as possible in order to eliminate the machine overloads. After formalizing this problem, we perform an extensive analysis of its parameterized complexity with respect to several natural parameters, resulting in a detailed picture of the problem’s complexity.
Cite as

Niels Grüttemeier and Klaus Heeger. Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.WADS.2025.31,
  author =	{Gr\"{u}ttemeier, Niels and Heeger, Klaus},
  title =	{{Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.31},
  URN =		{urn:nbn:de:0030-drops-242624},
  doi =		{10.4230/LIPIcs.WADS.2025.31},
  annote =	{Keywords: Job shop, parallel machines, reactive scheduling}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.75
Temporal Graph Realization with Bounded Stretch

Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time steps, where Δ 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 Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be 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 radius-algorithm) which always guarantees an approximation strictly smaller than Δ, 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.
Cite as

George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Temporal Graph Realization with Bounded Stretch. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2025.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Morawietz, Nils and Spirakis, Paul G.},
  title =	{{Temporal Graph Realization with Bounded Stretch}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{75:1--75:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.75},
  URN =		{urn:nbn:de:0030-drops-241829},
  doi =		{10.4230/LIPIcs.MFCS.2025.75},
  annote =	{Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, stretch}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.21
Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

Authors: Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
We study the complexity of the directed periodic temporal graph realization problem. This work is motivated by the design of periodic schedules in public transport with constraints on the quality of service. Namely, we require that the fastest path between (important) pairs of vertices is upper bounded by a specified maximum duration, encoded in an upper distance matrix D. While previous work has considered the undirected version of the problem, the application in public transport schedule design requires the flexibility to assign different departure times to the two directions of an edge. A problem instance can only be feasible if all values of the distance matrix are at least shortest path distances. However, the task of realizing exact fastest path distances in a periodic temporal graph is often too restrictive. Therefore, we introduce a minimum slack parameter k that describes a lower bound on the maximum allowed waiting time on each path. We concentrate on tree topologies and provide a full characterization of the complexity landscape with respect to the period Δ and the minimum slack parameter k, showing a sharp threshold between NP-complete cases and cases which are always realizable. We also provide hardness results for the special case of period Δ = 2 for general directed and undirected graphs.
Cite as

Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 21:1-21:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:LIPIcs.SAND.2025.21,
  author =	{Meusel, Julia and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{21:1--21:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.21},
  URN =		{urn:nbn:de:0030-drops-230747},
  doi =		{10.4230/LIPIcs.SAND.2025.21},
  annote =	{Keywords: Temporal graph, fastest temporal path, graph realization, periodic scheduling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.64
Cluster Editing on Cographs and Related Classes

Authors: Manuel Lafond, Alitzel López Sánchez, and Weidong Luo

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In the Cluster Editing problem, sometimes known as (unweighted) Correlation Clustering, we must insert and delete a minimum number of edges to achieve a graph in which every connected component is a clique. Owing to its applications in computational biology, social network analysis, machine learning, and others, this problem has been widely studied for decades and is still undergoing active research. There exist several parameterized algorithms for general graphs, but little is known about the complexity of the problem on specific classes of graphs. Among the few important results in this direction, if only deletions are allowed, the problem can be solved in polynomial time on cographs, which are the P₄-free graphs. However, the complexity of the broader editing problem on cographs is still open. We show that even on a very restricted subclass of cographs, the problem is NP-hard, W[1]-hard when parameterized by the number p of desired clusters, and that time n^o(p/log p) is forbidden under the ETH. This shows that the editing variant is substantially harder than the deletion-only case, and that hardness holds for the many superclasses of cographs (including graphs of clique-width at most 2, perfect graphs, circle graphs, permutation graphs). On the other hand, we provide an almost tight upper bound of time n^O(p), which is a consequence of a more general n^O(cw⋅p) time algorithm, where cw is the clique-width. Given that forbidding P₄s maintains NP-hardness, we look at {P₄, C₄}-free graphs, also known as trivially perfect graphs, and provide a cubic-time algorithm for this class.
Cite as

Manuel Lafond, Alitzel López Sánchez, and Weidong Luo. Cluster Editing on Cographs and Related Classes. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 64:1-64:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lafond_et_al:LIPIcs.STACS.2025.64,
  author =	{Lafond, Manuel and L\'{o}pez S\'{a}nchez, Alitzel and Luo, Weidong},
  title =	{{Cluster Editing on Cographs and Related Classes}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{64:1--64:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.64},
  URN =		{urn:nbn:de:0030-drops-228895},
  doi =		{10.4230/LIPIcs.STACS.2025.64},
  annote =	{Keywords: Cluster editing, cographs, parameterized algorithms, clique-width, trivially perfect graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.36
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Authors: Arnaud Casteigts, Nils Morawietz, and Petra Wolf

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph 𝒢 is from being transitive, namely, vertex-deletion distance to transitivity and arc-modification distance to transitivity, both being applied to the reachability graph of 𝒢. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.
Cite as

Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.MFCS.2024.36,
  author =	{Casteigts, Arnaud and Morawietz, Nils and Wolf, Petra},
  title =	{{Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.36},
  URN =		{urn:nbn:de:0030-drops-205923},
  doi =		{10.4230/LIPIcs.MFCS.2024.36},
  annote =	{Keywords: Temporal graphs, Parameterized complexity, Reachability, Transitivity}
}
  • Refine by Type
  • 34 Document/PDF
  • 15 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 13 2025
  • 3 2024
  • 4 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 16 Wolf, Petra
  • 8 Morawietz, Nils
  • 6 Arrighi, Emmanuel
  • 6 Fernau, Henning
  • 3 de Oliveira Oliveira, Mateus
  • Show More...

  • Refine by Series/Journal
  • 30 LIPIcs
  • 3 OASIcs
  • 1 TGDK

  • Refine by Classification
  • 10 Theory of computation → Problems, reductions and completeness
  • 8 Theory of computation → Graph algorithms analysis
  • 7 Theory of computation → Design and analysis of algorithms
  • 5 Mathematics of computing → Discrete mathematics
  • 4 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 5 Computational complexity
  • 3 Temporal graph
  • 3 graph realization
  • 2 Graph Drawing
  • 2 Reset sequence
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact