67 Search Results for "Erlebach, Thomas"

Volume

OASIcs, Volume 14

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)

ATMOS 2010, September 9, 2010, Liverpool, United Kingdom

Editors: Thomas Erlebach and Marco Lübbecke

Document
DOI: 10.4230/LIPIcs.SAND.2026.14
Robust Temporal Cut

Authors: Jessica Enright, Thomas Erlebach, Kitty Meeks, and Nils Morawietz

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
In this paper we introduce the Robust Temporal Cut problem (RTC) defined as follows: For a given temporal graph with designated source node s and destination node z, and parameters δ and k, remove a minimum number of time edges so that, even if an adversary can adjust the time labels of up to k of the remaining time edges by adding or subtracting values bounded by δ, no temporal s-z path exists. We study the classical and parameterized complexity of RTC. In particular, we show for both strict and non-strict temporal paths that RTC is NP-complete for any combination of k ≥ 1 and δ ≥ 1 and W[1]-hard for parameter solution size or vertex interval membership width plus pathwidth of the underlying graph. Furthermore, we give approximation algorithms and FPT algorithms for parameters including temporal neighborhood diversity plus solution size, timed vertex cover size, and vertex cover size of the underlying graph plus solution size.
Cite as

Jessica Enright, Thomas Erlebach, Kitty Meeks, and Nils Morawietz. Robust Temporal Cut. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{enright_et_al:LIPIcs.SAND.2026.14,
  author =	{Enright, Jessica and Erlebach, Thomas and Meeks, Kitty and Morawietz, Nils},
  title =	{{Robust Temporal Cut}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.14},
  URN =		{urn:nbn:de:0030-drops-262480},
  doi =		{10.4230/LIPIcs.SAND.2026.14},
  annote =	{Keywords: temporal graphs, minimum cut, parameterized complexity, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.24
Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries

Authors: Chirag Kaudan and Amir Nayyeri

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Eppstein, Goodrich, and Liu [ESA 2025] introduced a new graph parameter, called BFS-width, and gave polylogarithmic bounds on it for bounded bandwidth graphs. Their bounds naturally imply several applications, e.g. in graph reconstruction via shortest path distance queries, graph drawing, and matrix reordering. We study this parameter for a broader class of graphs, namely bounded cutwidth graphs. We prove a sublinear upper bound on the BFS-width of bounded cutwidth graphs and show that our bounds are asymptotically tight. Our upper bound implies the first deterministic algorithm for reconstructing a bounded cutwidth graph with a subquadratic number of shortest path distance queries.
Cite as

Chirag Kaudan and Amir Nayyeri. Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaudan_et_al:LIPIcs.SWAT.2026.24,
  author =	{Kaudan, Chirag and Nayyeri, Amir},
  title =	{{Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.24},
  URN =		{urn:nbn:de:0030-drops-260600},
  doi =		{10.4230/LIPIcs.SWAT.2026.24},
  annote =	{Keywords: Graph algorithms, graph theory, cutwidth, pathwidth, BFS-width}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.77
Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs

Authors: Malory Marin, Jean-Florent Raymond, and Rémi Watrigant

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the design of robust subexponential algorithms for classical connectivity problems on intersection graphs of similarly sized fat objects in ℝ^d. In this setting, each vertex corresponds to a geometric object, and two vertices are adjacent if and only if their objects intersect. We introduce a new tool for designing such algorithms, which we call a λ-linked partition. This is a partition of the vertex set into groups of highly connected vertices. Crucially, such a partition can be computed in polynomial time and does not require access to the geometric representation of the graph. We apply this framework to problems related to paths and cycles in graphs. First, we obtain the first robust ETH-tight algorithms for Hamiltonian Path and Hamiltonian Cycle, running in time 2^O(n^{1-1/d}) on intersection graphs of similarly sized fat objects in ℝ^d. This resolves an open problem of de Berg et al. [STOC 2018] and completes the study of these problems on geometric intersection graphs from the viewpoint of ETH-tight exact algorithms. We further extend our approach to the parameterized setting and design the first robust subexponential parameterized algorithm for Long Path in any fixed dimension d. More precisely, we obtain a randomized robust algorithm running in time 2^O(k^{1-1/d} log² k) n^O(1) on intersection graphs of similarly sized fat objects in ℝ^d, where k is the natural parameter. Besides λ-linked partitions, our algorithm also relies on a low-treewidth pattern covering theorem that we establish for geometric intersection graphs, which may be viewed as a refinement of a result of Marx-Pilipczuk [ESA 2017]. This structural result may be of independent interest.
Cite as

Malory Marin, Jean-Florent Raymond, and Rémi Watrigant. Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{marin_et_al:LIPIcs.SoCG.2026.77,
  author =	{Marin, Malory and Raymond, Jean-Florent and Watrigant, R\'{e}mi},
  title =	{{Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{77:1--77:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.77},
  URN =		{urn:nbn:de:0030-drops-258842},
  doi =		{10.4230/LIPIcs.SoCG.2026.77},
  annote =	{Keywords: Robust algorithms, geometric intersection graphs, subexponential FPT algorithms}
}
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.STACS.2026.32
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Authors: Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter

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

Abstract
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values of these parameters can be determined by performing costly queries. The goal is to design an adaptive query strategy that minimizes the query cost incurred in computing an optimal solution. Solving such problems generally requires that we be able to solve the associated verification problem: given the answers to all queries in advance, find a minimum-cost set of queries that certifies an optimal solution to the combinatorial optimization problem. We present a polynomial-time algorithm for verifying a minimum-weight basis of a matroid, where each weight lies in a given uncertainty area. These areas may be finite sets, real intervals, or unions of open and closed intervals, strictly generalizing previous work by Erlebach and Hoffman which only handled the special case of open intervals. Our algorithm introduces new techniques to address the resulting challenges. Verification problems are of particular importance in the area of explorable uncertainty, as the structural insights and techniques used to solve the verification problem often heavily influence work on the corresponding online problem and its stochastic variant. In our case, we use structural results from the verification problem to give a best-possible algorithm for a promise variant of the corresponding adaptive online problem. Finally, we show that our algorithms can be applied to two learning-augmented variants of the minimum-weight basis problem under explorable uncertainty.
Cite as

Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{diwan_et_al:LIPIcs.STACS.2026.32,
  author =	{Diwan, Haya and Hellerstein, Lisa and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-255216},
  doi =		{10.4230/LIPIcs.STACS.2026.32},
  annote =	{Keywords: Matroid verification, minimum-weight basis, query strategy, uncertainty matroid, explorable uncertainty}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.7
Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints

Authors: Christina Büsing, Maurice Draeger, and Corinna Mathwieser

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

Abstract
We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the sum of completion times (P|gen-prec, p_j = 1|γ, γ ∈ {C_max,∑_jC_j}). In our setting, each job is equipped with a Boolean formula (precedence constraint) over the set of jobs. A schedule satisfies a job’s precedence constraint if setting earlier jobs to true satisfies the formula. Our definition generalizes several common types of precedence constraints: classical and-constraints if every formula is a conjunction, or-constraints if every formula is a disjunction, and and/or-constraints if every formula is in conjunctive normal form. We prove fixed-parameter tractability when parameterizing by the number of predecessors. For parameterization by the number of successors, however, the complexity depends on the structure of the precedence constraints. If every constraint is a conjunction or a disjunction, we prove the problem to be fixed-parameter tractable. For constraints in disjunctive normal form, we prove W[1]-hardness. We show that the and/or-constrained problem is NP-hard, even for a single successor. Moreover, we prove NP-hardness on two machines if every constraint is a conjunction or a disjunction. This result not only proves para-NP-hardness for parameterization by the number of machines but also complements the polynomial-time solvability on two machines if every constraint is a conjunction [Coffman and Graham, 1972] or if every constraint is a disjunction [Johannes, 2005].
Cite as

Christina Büsing, Maurice Draeger, and Corinna Mathwieser. Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{busing_et_al:LIPIcs.IPEC.2025.7,
  author =	{B\"{u}sing, Christina and Draeger, Maurice and Mathwieser, Corinna},
  title =	{{Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{7:1--7:16},
  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.7},
  URN =		{urn:nbn:de:0030-drops-251390},
  doi =		{10.4230/LIPIcs.IPEC.2025.7},
  annote =	{Keywords: scheduling, precedence constraints, fixed-parameter tractability, complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.30
Approximating Optimal Broadcast of Files in a Hose-Model Network

Authors: Thomas Erlebach, Naveen Garg, Sukriti Gupta, and Amitabh Trehan

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The paper considers the problem of file sharing among peers who are connected to a common core network through links of differing upload and download capacities, as is the case in networks provisioned according to the hose model. The file is assumed to be divided into equal-sized chunks, and a peer can start sending a "chunk" of the file to another peer only after it has received the entire chunk. The objective is to share a chunk, initially residing on one of the peers, with all other peers in the least time possible. Peers can simultaneously send/receive parts of a chunk to/from multiple peers, subject to the upload and download capacity constraints. We only consider the problem of broadcasting one chunk to all peers. We consider two different models - in the migratory model, a peer can receive the chunk from multiple peers, while in the non-migratory model, any peer can receive the chunk only from one peer. For the migratory model, introduced in this paper, we show a novel integer program and use the optimum solution to the LP-relaxation to give a schedule with makespan e^{1/e} OPT+P where P is the time required by the slowest peer to download the chunk. Minimising makespan in the non-migratory model is known to be NP-hard. We give a solution with makespan 18OPT+P and this is the first approximation algorithm for heterogeneous and asymmetric upload/download capacities. We also consider 2 special cases. For uniform download capacities, we obtain a solution with makespan 2OPT extending a result due to Liu [Pangfeng Liu, 2002]. For uniform upload capacities, we give the first approximation algorithm, producing makespan at most 2OPT+2P.
Cite as

Thomas Erlebach, Naveen Garg, Sukriti Gupta, and Amitabh Trehan. Approximating Optimal Broadcast of Files in a Hose-Model Network. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.FSTTCS.2025.30,
  author =	{Erlebach, Thomas and Garg, Naveen and Gupta, Sukriti and Trehan, Amitabh},
  title =	{{Approximating Optimal Broadcast of Files in a Hose-Model Network}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.30},
  URN =		{urn:nbn:de:0030-drops-251118},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.30},
  annote =	{Keywords: File sharing, scheduling, peer-to-peer networks}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.8
Parameterized Algorithms for the Drone Delivery Problem

Authors: Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin

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

Abstract
Timely delivery and optimal routing remain fundamental challenges in the modern logistics industry. Building on prior work that considers single-package delivery across networks using multiple types of collaborative agents with restricted movement areas (e.g., drones or trucks), we examine the complexity of the problem under structural and operational constraints. Our focus is on minimizing total delivery time by coordinating agents that differ in speed and movement range across a graph. This problem formulation aligns with the recently proposed Drone Delivery Problem with respect to delivery time (DDT), introduced by Erlebach et al. [ISAAC 2022]. We first resolve an open question posed by Erlebach et al. [ISAAC 2022] by showing that even when the delivery network is a path graph, DDT admits no polynomial-time approximation within any polynomially encodable factor a(n), unless P=NP. Additionally, we identify the intersection graph of the agents, where nodes represent agents and edges indicate an overlap of the movement areas of two agents, as an important structural concept. For path graphs, we show that DDT becomes tractable when parameterized by the treewidth w of the intersection graph, and we present an exact FPT algorithm with running time f(w)⋅poly(n,k), for some computable function f. For general graphs, we give an FPT algorithm with running time f(Δ,w)⋅poly(n,k), where Δ is the maximum degree of the intersection graph. In the special case where the intersection graph is a tree, we provide a simple polynomial-time algorithm.
Cite as

Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin. Parameterized Algorithms for the Drone Delivery Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bartlmae_et_al:LIPIcs.ISAAC.2025.8,
  author =	{Bartlmae, Simon and Hene, Andreas and K\"{o}nen, Joshua and R\"{o}glin, Heiko},
  title =	{{Parameterized Algorithms for the Drone Delivery Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{8:1--8:16},
  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.8},
  URN =		{urn:nbn:de:0030-drops-249162},
  doi =		{10.4230/LIPIcs.ISAAC.2025.8},
  annote =	{Keywords: Complexity, Delivery, FPT algorithms, Graph Theory}
}
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.ISAAC.2025.23
Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

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

Abstract
Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.
Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  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.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.27
Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

Authors: Michelle Döring

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

Abstract
Temporal graphs model networks whose connections are available only at specific points in time. Several definitional subtleties - whether paths must follow strictly increasing time labels (strict vs. non-strict), whether adjacent edges cannot appear simultaneously (proper), and whether edges are forbidden to appear multiple times (simple) - give rise to different temporal graph settings. These distinctions directly impact the definition of temporal reachability, a core concept in temporal graph theory. Casteigts, Corsini, and Sarkar [TCS24] introduced a framework of equivalence notions to compare the expressive power of these settings focusing solely on undirected temporal graphs. In this work, we extend their framework to include the fundamental dimension of directed vs. undirected. Our contribution is three-fold. We (1) complete the undirected hierarchy by resolving the two open questions from [TCS24], (2) fully characterize the hierarchy of the directed settings, and (3) compare the directed and undirected settings, showing that directed temporal graphs are strictly more expressive than undirected temporal graphs in terms of reachability. Our structural results highlight both the limitations and strengths of various temporal graph settings - for example, directed + strict + simple graphs can realize every possible reachability graph, while directed + proper graphs necessarily induce at least one transitive reachability on each directed cycle. We also provide transformation procedures between temporal settings offering practical tools for transferring algorithms and hardness results across models.
Cite as

Michelle Döring. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doring:LIPIcs.ISAAC.2025.27,
  author =	{D\"{o}ring, Michelle},
  title =	{{Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{27:1--27:21},
  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.27},
  URN =		{urn:nbn:de:0030-drops-249353},
  doi =		{10.4230/LIPIcs.ISAAC.2025.27},
  annote =	{Keywords: temporal graphs, directed graphs, temporal reachability, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.41
Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Authors: Ashish Saxena and Kaushik Mondal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the exploration problem by mobile agents in Connectivity Time dynamic graphs. The Connectivity Time model was introduced by Michail et al. [JPDC 2014] and is arguably one of the weakest dynamic graph connectivity models. We prove that exploration is impossible in such graphs using ((n-1)(n-2))/2 mobile agents starting from an arbitrary initial configuration, even when agents have full knowledge of system parameters, global communication, full visibility, and infinite memory. We then present an exploration algorithm that uses ((n-1)(n-2))/2 + 1 agents equipped with global communication, 1-hop visibility and O(log n) memory.
Cite as

Ashish Saxena and Kaushik Mondal. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.DISC.2025.41,
  author =	{Saxena, Ashish and Mondal, Kaushik},
  title =	{{Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41},
  URN =		{urn:nbn:de:0030-drops-248585},
  doi =		{10.4230/LIPIcs.DISC.2025.41},
  annote =	{Keywords: Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Deterministic algorithm}
}
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/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}
}
  • Refine by Type
  • 66 Document/PDF
  • 29 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 5 2026
  • 25 2025
  • 5 2024
  • 3 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 25 Erlebach, Thomas
  • 6 Morawietz, Nils
  • 5 Luo, Kelin
  • 5 Megow, Nicole
  • 5 Schlöter, Jens
  • Show More...

  • Refine by Series/Journal
  • 48 LIPIcs
  • 17 OASIcs
  • 1 DagSemProc

  • Refine by Classification
  • 13 Theory of computation → Design and analysis of algorithms
  • 10 Theory of computation → Graph algorithms analysis
  • 7 Mathematics of computing → Discrete mathematics
  • 6 Theory of computation → Online algorithms
  • 3 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 explorable uncertainty
  • 3 Competitive analysis
  • 3 complexity
  • 3 graph realization
  • 3 parameterized complexity
  • 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