George Skretas

Paul Sievers, George Skretas, Georg Tennigkeit

Network redesign problems ask for modifications to the edges of a given graph to satisfy certain properties. In temporal graphs, where edges are only active at certain times, we are sometimes only allowed to modify when the edges are going to be active. In practice, we might not even be able to perform all of the necessary modifications at once; changes must be applied step-by-step while the network is still in operation, meaning that the network must continue to satisfy some properties. To initiate a study in this area, we introduce the class of temporal graph reconfiguration problems. As a starting point, we consider the Layered Connectivity Reconfiguration (LCR) problem: Given two always-connected temporal graphs G1 and G2, determine if it is possible to transform G1 into G2 by changing the time at which a single temporal edge is active in each step, such that every intermediate temporal graph is always-connected. We provide a dynamic programming algorithm for the LCR problem. We also show that finding the shortest reconfiguration sequence between two temporal graphs is APX-hard. Additionally, we show that the LCR problem is equivalent to the Spanning Tree Sequence Reconfiguration (STSR) problem introduced by Hanaka et al. Therefore, our results also answer the two open questions presented by the authors: (i) find a simpler algorithm for the STSR problem, (ii) show that the STSR problem is inapproximable up to some factor.

Argyrios Deligkas, Michelle Döring, Eduard Eiben et al.

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 unconstrained. 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.

Michelle Döring, Niklas Mohrin, George Skretas

We introduce the TemporallyEdgeDisjointScheduleCompletion (TEDSC) problem in which we need to cover a set of temporal edge demands $D$ by routing $k$ temporal walks through a directed static graph while remaining temporally edge disjoint. This problem combines the temporal aspects of train routing and passenger demands with the static nature of real-world rail networks. We present a polynomial time algorithm for TEDSC. Motivated by real world constraints, we next investigate two restricted variants of TEDSC in which each walk can only travel for some bounded distance or time $h$. We show that both are tractable when parameterized by $k + h$, but hard for $h$ and $k + |D|$. If we fix the underlying network, the two problems exhibit distinct complexities: The distance variant remains $W[1]$-hard parameterized by $k$ even on a path of three vertices whereas the time variant admits an FPT algorithm on any fixed star. Finally, we show how to approximate the number of required walks up to a factor of $(2-h^{-1})$.

Hans Gawendowicz, Nicolas Klodt, Aleksandrs Morgensterns et al.

A crucial aspect of research is understanding how real-world networks, such as transportation and information networks, are formed. A prominent model for such networks was introduced by \cite{fabrikant_network_2003} and extended by \cite{bilo_temporal_2023}, incorporating temporal graphs to better represent real-world networks. In this model, there is a given host graph with $n$ agents (represented by nodes) and time labels on the edges. Each agent can establish connections by purchasing edges. This makes the edges present at the time steps given by the time labels of the host graph. The goal of each agent is to reach as many other agents as possible while minimizing the number of edges bought. However, this model makes the simplifying assumption that each edge comes with predetermined time steps. We address this deficiency by extending the model of Bilo et al. \cite{bilo_temporal_2023} to allow agents to purchase edges and to decide when they appear. To capture a variety of real-world applications, we study two reachability models and several cost functions based on the label an agent assigns to an edge. For these settings, we provide proofs of existence of Nash equilibria, as well as lower and upper bounds on the Price of Anarchy and Price of Stability.

Davide Bilò, Sarel Cohen, Tobias Friedrich et al.

Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.

Othon Michail, George Skretas, Paul G. Spirakis

In this work, we study theoretical models of \emph{programmable matter} systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): \emph{rotate} around a neighbor and \emph{slide} over a line. In terms of modeling, there are $n$ nodes arranged in a 2-dimensional grid and forming some initial \emph{shape}. The goal is for the initial shape $A$ to \emph{transform} to some target shape $B$ by a sequence of movements. Most of the paper focuses on \emph{transformability} questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes $A$ and $B$ can be transformed to each other, is in $\mathbf{P}$. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in $\mathbf{PSPACE}$ and study the problem of determining the minimum \emph{seeds} that can make feasible, otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes $A,B$ of the same order, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is $Ω(n^2)$. We improve this to $O(n)$ parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. In the last part of the paper, we turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformations.