Thomas Erlebach

TCS Journal 2025 Journal Article

Parameterized algorithms for multi-label periodic temporal graph realization

• Thomas Erlebach
• Nils Morawietz
• Petra Wolf

In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n × n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D. We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to ℓ times in each period, for some given integer ℓ. For the resulting problem Multi-Label Periodic TGR, we show that it is fixed-parameter tractable for parameter n and for parameter vc + Δ, where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu + d max, where nu is the number of non-universal vertices of the underlying graph and d max is the largest entry of D. Furthermore, we show that the problem is NP-hard for each ℓ ≥ 5, even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if ℓ = 1.

IJCAI Conference 2023 Conference Paper

Sorting and Hypergraph Orientation under Uncertainty with Predictions

• Thomas Erlebach
• Murilo de Lima
• Nicole Megow
• Jens Schlöter

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to minimize the number of queries needed to solve a problem. We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty, assuming access to untrusted predictions for the uncertain values. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions. For sorting, our algorithm uses the optimal number of queries for accurate predictions and at most twice the optimal number for arbitrarily wrong predictions. For hypergraph orientation, for any γ≥2, we give an algorithm that uses at most 1+1/γ times the optimal number of queries for accurate predictions and at most γ times the optimal number for arbitrarily wrong predictions. These tradeoffs are the best possible. We also consider different error metrics and show that the performance of our algorithms degrades smoothly with the prediction error in all the cases where this is possible.

TCS Journal 2021 Journal Article

“Green” barrier coverage with mobile sensors

• Amotz Bar-Noy
• Thomas Erlebach
• Dror Rawitz
• Peter Terlecky

Mobile sensors are located on a barrier represented by a line segment. Each sensor has a single energy source that can be used for both moving and sensing. A sensor consumes energy in movement in proportion to distance traveled, and it expends energy per time unit for sensing in direct proportion to its radius raised to a constant exponent. We address the problem of energy efficient coverage. The input consists of the initial locations of the sensors and a coverage time requirement t. A feasible solution consists of an assignment of destinations and coverage radii to all sensors such that the barrier is covered. We consider two variants of the problem that are distinguished by whether the radii are given as part of the input. In the fixed radii case, we are also given a radii vector ρ, and the radii assignment r must satisfy r i ∈ { 0, ρ i }, for every i, while in the variable radii case the radii assignment is unrestricted. The goal is to cover the barrier for t time in an energy efficient manner. More specifically, we consider two objective functions. In the first the goal is to minimize the sum of the energy spent by all sensors and in the second the goal is to minimize the maximum energy used by any sensor. We present fully polynomial time approximation schemes for the problem of minimizing the energy sum with variable radii and for the problem of minimizing the maximum energy with variable radii. We also show that the latter can be approximated within any additive constant ε > 0. We present a 2-approximation algorithm for the problem of minimizing the maximum energy with fixed radii which also is shown to be strongly NP-hard. We show that the problem of minimizing the energy sum with fixed radii cannot be approximated within a factor of O ( n c ), for any constant c, unless P = NP. Additional results are given for three special cases: (i) sensors are stationary, (ii) free movement, and (iii) uniform fixed radii.

TCS Journal 2019 Journal Article

Complexity and online algorithms for minimum skyline coloring of intervals

• Thomas Erlebach
• Fu-Hong Liu
• Hsiang-Hsuan Liu
• Mordechai Shalom
• Prudence W.H. Wong
• Shmuel Zaks

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it.

MFCS Conference 2018 Conference Paper

Car-Sharing between Two Locations: Online Scheduling with Two Servers

• Kelin Luo
• Thomas Erlebach
• Yinfeng Xu

In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The length of the time interval between the submission of a request (booking time) and the pick-up time is fixed. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted. We present lower bounds on the competitive ratio for this problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.

MFCS Conference 2018 Conference Paper

Faster Exploration of Degree-Bounded Temporal Graphs

• Thomas Erlebach
• Jakob T. Spooner

A temporal graph can be viewed as a sequence of static graphs indexed by discrete time steps. The vertex set of each graph in the sequence remains the same; however, the edge sets are allowed to differ. A natural problem on temporal graphs is the Temporal Exploration problem (TEXP): given, as input, a temporal graph G of order n, we are tasked with computing an exploration schedule (i. e. , a temporal walk that visits all vertices in G), such that the time step at which the walk arrives at the last unvisited vertex is minimised (we refer to this time step as the arrival time). It can be easily shown that general temporal graphs admit exploration schedules with arrival time no greater than O(n^2). Moreover, it has been shown previously that there exists an infinite family of temporal graphs for which any exploration schedule has arrival time Omega(n^2), making these bounds tight for general TEXP instances. We consider restricted instances of TEXP, in which the temporal graph given as input is, in every time step, of maximum degree d; we show an O(n^2/log n) bound on the arrival time when d is constant, and an O(d log d * n^2/log n) bound when d is given as some function of n.

TCS Journal 2016 Journal Article

Query-competitive algorithms for cheapest set problems under uncertainty

• Thomas Erlebach
• Michael Hoffmann
• Frank Kammer

Considering the model of computing under uncertainty where element weights are uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimum-weight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d ⋅ OPT + d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multi-cut problem in trees with d terminal pairs, we give an algorithm that makes at most d ⋅ OPT + 1 queries. For the problem of computing a minimum-weight base of a given matroid, we give an algorithm that makes at most 2 ⋅ OPT queries, generalizing a known result for the minimum spanning tree problem. For each of the above algorithms we give matching lower bounds. We also settle the complexity of the verification version of the general cheapest set problem and the minimum multi-cut problem in trees under uncertainty.

TCS Journal 2015 Journal Article

Computational complexity of traffic hijacking under BGP and S-BGP

• Marco Chiesa
• Giuseppe Di Battista
• Thomas Erlebach
• Maurizio Patrignani

Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E. g. , we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

TCS Journal 2014 Journal Article

Editorial for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities

• Amotz Bar-Noy
• Thomas Erlebach
• Magnús M. Halldórsson
• Sotiris Nikoletseas
• Pekka Orponen

TCS Journal 2010 Journal Article

Discovery of network properties with all-shortest-paths queries

• Davide Bilò
• Thomas Erlebach
• Matúš Mihalák
• Peter Widmayer

We consider the problem of discovering properties (such as the diameter) of an unknown network G = ( V, E ) with a minimum number of queries. Initially, only the vertex set V of the network is known. Information about the edges and non-edges of the network can be obtained by querying nodes of the network. A query at a node q ∈ V returns the union of all shortest paths from q to all other nodes in V. We study the problem as an online problem–an algorithm does not initially know the edge set of the network, and has to decide where to make the next query based on the information that was gathered by previous queries. We study how many queries are needed to discover the diameter, a minimal dominating set, a maximal independent set, the minimum degree, and the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2-edge or 2-vertex connected. We use the usual competitive analysis to evaluate the quality of online algorithms, i. e. , we compare online algorithms with the optimum offline algorithms. For all properties except the maximal independent set, 2-vertex connectivity and minimum/maximum degree, we present and analyze online algorithms. Furthermore we show, for all the aforementioned properties, that “many” queries are needed in the worst case. As our query model delivers more information about the network than the measurement heuristics that are currently used in practice, these negative results suggest that a similar behavior can be expected in realistic settings, or in more realistic models derived from the all-shortest-paths query model.

SODA Conference 2008 Conference Paper

Approximating geometric coverage problems

• Thomas Erlebach
• Erik Jan van Leeuwen

SODA Conference 2008 Conference Paper

Broadcast scheduling: algorithms and complexity

• Jessica Chang
• Thomas Erlebach
• Renars Gailis
• Samir Khuller

SODA Conference 2002 Conference Paper

NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

• Thomas Erlebach
• Alexander Hall

MFCS Conference 2001 Conference Paper

Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings

• Thomas Erlebach

Abstract A tree of rings is a network that is obtained by interconnecting rings in a tree structure such that any two rings share at most one node. A connection request (call) in a tree of rings is given by its two endpoints and, in the case of prespecified paths, a path connecting these two endpoints. We study undirected trees of rings as well as bidirected trees of rings. In both cases, we show that the path packing problem (assigning paths to calls so as to minimize the maximum load) can be solved in polynomial time, that the path coloring problem with prespecified paths can be approximated within a constant factor, and that the maximum (weight) edge-disjoint paths problem is \( \mathcal{N}\mathcal{P} \) -hard and can be approximated within a constant factor (no matter whether the paths are prespecified or can be determined by the algorithm). We also consider fault-tolerance in trees of rings: If a set of calls has been established along edge-disjoint paths and if an arbitrary link fails in every ring of the tree of rings, we show that at least one third of the calls can be recovered if rerouting is allowed. Furthermore, computing the optimal number of calls that can be recovered is shown to be polynomial in undirected trees of rings and \( \mathcal{N}\mathcal{P} \) -hard in bidirected trees of rings.

TCS Journal 2001 Journal Article

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

• Thomas Erlebach
• Peter Rossmanith
• Hans Stadtherr
• Angelika Steger
• Thomas Zeugmann

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2 logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4 logn) (cf. Angluin, J. Comput. Systems Sci. 21(1) (1980) 46–62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/log n) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ2 logℓ) provided the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.

SODA Conference 2001 Conference Paper

Polynomial-time approximation schemes for geometric graphs

• Thomas Erlebach
• Klaus Jansen
• Eike Seidel

TCS Journal 2001 Journal Article

The complexity of path coloring and call scheduling

• Thomas Erlebach
• Klaus Jansen

Modern high-performance communication networks pose a number of challenging problems concerning the efficient allocation of resources to connection requests. In all-optical networks with wavelength-division multiplexing, connection requests must be assigned paths and colors (wavelengths) such that intersecting paths receive different colors, and the goal is to minimize the number of colors used. This path coloring problem is proved NP -hard for undirected and bidirected ring networks. Path coloring in undirected tree networks is shown to be equivalent to edge coloring of multigraphs, which implies a polynomial-time optimal algorithm for trees of constant degree as well as NP -hardness and an approximation algorithm with absolute approximation ratio 4 3 and asymptotic approximation ratio 1. 1 for trees of arbitrary degree. For bidirected trees, path coloring is shown to be NP -hard even in the binary case. A polynomial-time optimal algorithm is given for path coloring in undirected or bidirected trees with n nodes under the assumption that the number of paths touching every single node of the tree is O((logn)1−ε). Call scheduling is the problem of assigning paths and starting times to calls in a network with bandwidth reservation such that the maximum completion time is minimized. In the case of unit bandwidth requirements, unit edge capacities, and unit call durations, call scheduling is equivalent to path coloring. If either the bandwidth requirements or the call durations can be arbitrary, call scheduling is shown NP -hard for virtually every network topology.

TCS Journal 1999 Journal Article

Optimal wavelength routing on directed fiber trees

• Thomas Erlebach
• Klaus Jansen
• Christos Kaklamanis
• Milena Mihail
• Pino Persiano

We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load L per directed fiber link on a directed fiber tree using at most 5/3L wavelengths. This improves previous results of Raghavan and Upfal (Proc. Ann. ACM Symp. on theory of computing STOC, 1994, pp. 134–143), Mihail et al. (Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 548–557), Kaklamanis and Persiano (Proc. Algorithms — ESA 96, Lecture Notes in Computer Science, 1136, pp. 460–470), Kumar and Schwabe (Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA, 1997, pp. 437–444). We also prove that no greedy algorithm can in general use less than 5/3L wavelengths for a set of requests of load L in a directed fiber tree, and thus our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in [8–10, 12].