We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of k temporal paths, i.e., every given path is a sequence of edges with strictly increasing labels that denote availability in time. This type of temporal graphs represent train networks. We consider shifting operations on the labels of the paths that maintain their temporal continuity. This means that we can move the availability of a temporal edge later or earlier in time, and propagate the shifts to all other affected edges of the path in order to preserve its temporal connectivity. We study the parameterized complexity of the problem with respect to the number of paths k, and the total budget b, where b is the maximum number of shifts we are allowed to perform. Our results reveal that fixed parameter tractability can be achieved (1) when parameterized both by k and b, and (2) when parameterized by k, and b is unlimited. In almost every other case, e.g., parameterized by a single parameter or parameterized by k, while having a bound on b, we establish intractability lower bounds that are matched by XP algorithms.

Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.

To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound B on the number of 1-bits allowed in the length- n bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where B bits have a weight of 1+ 1/ n and the remaining bits have a weight of 1. Friedrich et al. [TCS 2020] gave a bound of Θ ( n 2 ) for the expected running time of the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a 1 and a 0 simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in O(n log n ) if n-B = O (1). However, if n-B = Θ ( n ), we show a bound of Ω ( n 2 ), just as for classic bit mutation. Crossover together with a simple island model gives running times of O ( n 2 / log n ) (uniform crossover) and \(O(n\sqrt {n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity, we show a bound of O ( n log n ). As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.

In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound B on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where B bits have a weight of 1 + ε and the remaining bits have a weight of 1. The literature gives a bound of Θ(n2) for the (1+1) EA on this function.