SAND 3rd edition (2024)
June 5-7, 2024
University of Patras, GREECE
University of Patras, GREECE
| Home | CFP | Accepted | Program | Venue | Registration |
| (REG) | Temporal graph realization from fastest paths |
| Nina Klobas, George Mertzios, Hendrik Molter and Paul Spirakis | |
| In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal graphs. Given an $n \times n$ matrix $D$ and a $\Delta \in \mathbb{N}$, the goal is to construct a $\Delta$-periodic temporal graph with $n$ vertices such that the duration of a fastest path from $v_i$ to $v_j$ is equal to $D_{i,j}$, or to decide that such a temporal graph does not exist. The variations of the problem on static graphs has been well studied and understood since the 1960's (e.g. [Erdos and Gallai, 1960], [Hakimi and Yau, 1965]). As it turns out, the periodic temporal graph realization problem has a very different computational complexity behavior than its static (i.e. non-temporal) counterpart. First we show that the problem is NP-hard in general, but polynomial-time solvable if the so-called underlying graph is a tree. Building upon those results, we investigate its parameterized computational complexity with respect to structural parameters of the underlying static graph which measure the ``tree-likeness''. We prove a tight classification between such parameters that allow fixed-parameter tractability (FPT) and those which imply W[1]-hardness. We show that our problem is W[1]-hard when parameterized by the feedback vertex number (and therefore also any smaller parameter such as treewidth, degeneracy, and cliquewidth) of the underlying graph, while we show that it is in FPT when parameterized by the feedback edge number (and therefore also any larger parameter such as maximum leaf number) of the underlying graph. |
| (REG) | Computational Power of Opaque Robots |
| Caterina Feletti, Lucia Mambretti, Carlo Mereghetti and Beatrice Palano | |
| In the field of distributed computing by robot swarms, the research comprehends manifold models where robots operate in the Euclidean plane through a sequence of look-compute-move cycles. Models under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, and (iii) the synchronization mode. By varying features (i,ii), we obtain the noted four base models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Combining each base model with the three main synchronization modes (fully synchronous, semi-synchronous, and asynchronous), we obtain the well-known 12 models. Extensive research has studied their computational power, proving the hierarchical relations between different models. However, only transparent robots have been considered. In this work, we study the taxonomy of the 12 models considering collision-intolerant opaque robots. We present six witness problems that prove the majority of the computational relations between the 12 models. In particular, the last witness problem depicts a peculiar issue occurring in the case of obstructed visibility and asynchrony. |
| (REG) | Harmonious Colourings of Temporal Matchings |
| Duncan Adamson | |
| Graph colouring is a fundamental problem in computer science, with a large body of research dedicated to both the general colouring problem and restricted cases. Harmonious colourings are one such restriction, where each edge must contain a globally unique pair of colours, i.e. if an edge connects a vertex coloured x with a vertex coloured y, then no other pair of connected vertices can be coloured x and y. Finding such a colouring in the traditional graph setting is known to be NP-hard, even in trees. This paper considers the generalisation of harmonious colourings to Temporal Graphs, specifically (k,t)-Temporal matchings, a class of temporal graphs where the underlying graph is a matching (a collection of disconnected components containing pairs of vertices), each edge can appear in at most t timesteps, and each timestep can contain at most k other edges. We provide a complete overview of the complexity landscape of finding temporal harmonious colourings for (k,t)-matchings. We show that finding a Temporal Harmonious Colouring, a colouring that is harmonious in each timestep, is NP-hard for (k,t)-Temporal Matchings when k ≥ 4, t ≥ 2, or when k ≥ 2 and t ≥ 3. We further show that this problem is inapproximable for t ≥ 2 and an unbounded value of k, and that the problem of determining the temporal harmonious chromatic number of a (2,3)-temporal matching can be determined in linear time. Finally, we strengthen this result by a set of upper and lower bounds of the temporal harmonious chromatic number both for individual temporal matchings and for the class of (k, t)-temporal matchings. |
| (REG) | Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization |
| Thomas Erlebach, Nils Morawietz and Petra Wolf | |
| In the periodic temporal graph realization problem introduced by Klobas et al. (arXiv:2302.08860 [cs.DS]) one is given a period $\Delta$ and an $n\times n$ matrix $D$ of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period $\Delta$ 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 $\ell$ times in each period, for some given integer $\ell$. For the resulting problem Multi-Label Periodic TGR, we show that it is fixed-parameter tractable for parameter $n$ and for parameter $\mathrm{vc}+\Delta$, where $\mathrm{vc}$ is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter $k+d_{max}$, where $k$ 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 $\ell \geq 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 $\ell = 1$. |
| (REG) | On the Complexity of Temporal Arborescence Reconfiguration |
| Riccardo Dondi and Manuel Lafond | |
| We analyze the complexity of Arborescence Reconfiguration on temporal digraphs (Temporal 6 Arborescence Reconfiguration). The problem, given two temporal arborescences in a temporal digraph, asks for the minimum number of arc flips, i.e. arc exchanges, that result in a sequence of temporal arborescences that transforms the given one into the other. We analyze the complexity of the problem, taking into account also its approximation and parameterized complexity, even in restricted cases. First, we solve an open problem showing that Temporal Arborescence Reconfiguration is NP-hard for two timestamps. Then we show that even if the two temporal arborescences differ only for two arc pairs, then the problem is not approximable within factor b ln |V (D)|, for any constant 0 < b < 1, where V (D) is the set of vertices of the temporal arborescences. Finally, we prove that Temporal Arborescence Reconfiguration is W[1]-hard when parameterized by the number of arc flips needed to transform one temporal arborescence into the other. |
| (REG) | Reconfiguration and Locomotion with Joint Movements in the Amoebot Model |
| Andreas Padalkin, Manish Kumar and Christian Scheideler | |
| We are considering the geometric amoebot model where a set of $n$ \emph{amoebots} is placed on the triangular grid. An amoebot is able to send information to its neighbors, and to move via expansions and contractions. Since amoebots and information can only travel node by node, most problems have a natural lower bound of $\Omega(D)$ where $D$ denotes the diameter of the structure. Inspired by the nervous and muscular system, Feldmann et al. have proposed the \emph{reconfigurable circuit extension} and the \emph{joint movement extension} of the amoebot model with the goal of breaking this lower bound. In the joint movement extension, the way amoebots move is altered. Amoebots become able to push and pull other amoebots. Feldmann et al. demonstrated the power of joint movements by transforming a line of amoebots into a rhombus within $O(\log n)$ rounds. However, they left the details of the extension open. The goal of this paper is therefore to formalize and extend the joint movement extension. In order to provide a proof of concept for the extension, we consider two fundamental problems of modular robot systems: \emph{shape formation} and \emph{locomotion}. We approach these problems by defining meta-modules of rhombical and hexagonal shape, respectively. The meta-modules are capable of movement primitives like sliding, rotating, and tunneling. This allows us to simulate shape formation algorithms of various modular robot systems. Finally, we construct three amoebot structures capable of locomotion by rolling, crawling, and walking, respectively. |
| (REG) | An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes |
| Shuma Kumamoto, Shuji Kijima and Tomoyuki Shirai | |
| It is a cerebrated fact that a simple random walk on an infinite k-ary tree returns to the initial vertex at most finitely many times during infinitely many transitions; it is called transient. This work points a fact that a simple random walk on an infinitely growing k-ary tree can return to the initial vertex infinitely many times, it is called recurrent, depending on the growing speed of the tree. Precisely, this paper is concerned with a simple specific model of a random walk on a growing graph (RWoGG), and shows a phase transition between the recurrence and transience of the random walk regarding the growing speed of the graph. To prove the phase transition, we develop a (type of) coupling argument, introducing the notion of less homesick as graph growing (LHaGG). We also show some other examples, including a random walk on {0,1}^n with an infinitely growing n, of the phase transition between the recurrence and transience. We remark that some graphs concerned in this paper have infinitely growing degrees. |
| (REG) | All for one and one for all: An O(1)-Musketeers Universal Transformation for Rotating Robots |
| Matthew Connor, Othon Michail and George Skretas | |
| In this paper, we settle the main open question of $[$Michail, Skretas, Spirakis, ICALP'17$]$, asking what is the family of two-dimensional geometric shapes that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of interconnected modules that perform the minimal mechanical operation of $90\degree$ rotations around each other. The goal is to transform an initial shape of modules $A$ into a target shape $B$. Under the necessary assumptions that the given shapes are connected and have identical colourings on a checkered colouring of the grid, and using a seed of only constant size, we prove that any pair of such shapes can be transformed into each other within an optimal $O(n^2)$ rotation operations none of which disconnects the shape. |
| (REG) | Fault-Tolerant Distributed Directories |
| Judith Beestermöller, Costas Busch and Roger Wattenhofer | |
| Many fundamental distributed computing problems require coordinated access to a shared resource. A distributed directory is an overlay data structure on an asynchronous graph $G$ that helps to access a shared token $t$. The directory supports three basic operations: {\em publish}, to initialize the directory, {\em lookup}, to read the contents of the token, and {\em move}, to get exclusive update access to the token. There are known directory schemes that achieve message complexity within polylog factors of the optimal cost with respect to the number of nodes $n$ and the diameter $D$ of $G$. Motivated by fault-tolerant distributed computing implementations, we consider the impact of edge failures on distributed directories. We give a distributed directory overlay data structure that can tolerate edge failures without disrupting the directory operations. The directory can be repaired concurrently while it processes directory operations. We analyze the impact of the faults on the amortized cost of the three directory operations compared to the optimal cost. We show that $f$ edges failures increase the amortized competitive ratio of the operations by at most factor $f$. We also analyze the message complexity to repair the overlay structure, in terms of the number of messages that are sent and the maximum distance a message traverses. For an edge failure, the repair mechanism uses messages of size $\mathcal{O}(\log n)$ that traverse distance at most $D'$, the graph diameter after the fault. To our knowledge, this is the first asymptotic analysis of a fault-tolerant distributed directory. |
| (REG) | Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures |
| Kristian Hinnenthal, David Liedtke and Christian Scheideler | |
| This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pick-up, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an \emph{icicle}. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in $\mathcal{O}(n^3)$ steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average. |
| (REG) | Space and Move-optimal Arbitrary Pattern Formation on infinite rectangular grid by oblivious robot swarm |
| Avisek Sharma, Satakshi Ghosh, Pritam Goswami and Buddhadeb Sau | |
| Arbitrary Pattern Formation (APF) is a fundamental coordination problem in swarm robotics. It requires a set of autonomous robots (mobile computing units) to form an arbitrary pattern (given as input) starting from any initial pattern. This problem has been extensively investigated in continuous and discrete scenarios, with this study focusing on the discrete variant. A set of robots is placed on the nodes of an infinite rectangular grid graph embedded in the euclidean plane. The movements of the robots are restricted to one of the four neighboring grid nodes from its current position. The robots are autonomous, anonymous, identical, and homogeneous, and operate Look-Compute-Move cycles. In this work, we adopt the classical $\mathcal{OBLOT}$ robot model, meaning the robots have no persistent memory or explicit communication methods, yet they possess full and unobstructed visibility. This work proposes an algorithm that solves the APF problem in a fully asynchronous scheduler assuming the initial configuration is asymmetric. The considered performance measures of the algorithm are space and number of moves required for the robots. The algorithm is asymptotically move-optimal. Here, we provide a definition of space complexity that takes the visibility issue into consideration. We observe an obvious lower bound $\mathcal{D}$ of the space complexity and show that the proposed algorithm has the space complexity $\mathcal{D}+4$. On comparing with previous related works, we show that this is the first proposed algorithm considering $\mathcal{OBLOT}$ robot model that is asymptotically move-optimal and has the least space complexity which is almost optimal. |
| (REG) | Complexity of Boolean automata networks under block-parallel update modes |
| Kévin Perrot, Sylvain Sené and Léah Tapin | |
| Boolean automata networks (aka Boolean networks) are space-time discrete dynamical systems, studied as a model of computation and as a representative model of natural phenomena. A collection of simple entities (the automata) update their 0-1 states according to local rules. The dynamics of the network is highly sensitive to update modes, i.e., to the schedule according to which the automata apply their local rule. A new family of update modes appeared recently, called block-parallel, which is dual to the well studied block-sequential. Although basic, it embeds the rich feature of update repetitions among a temporal updating period, allowing for atypical asymptotic behaviors. In this paper, we prove that it is able to breed complex computations, squashing almost all decision problems on the dynamics to the traditionally highest (for reachability questions) class PSPACE. Despite obtaining these complexity bounds for a broad set of local and global properties, we also highlight a surprising gap: bijectivity is still coNP. |
| (REG) | Online Space-time Travel Planning in Dynamic Graphs |
| Quentin Bramas, Jean-Romain Luttringer and Sebastien Tixeuil | |
| We study the problem of traveling on an unknown dynamic graph to reach a destination with the minimum latency. At each step of the execution, an agent can decide to move to a neighboring node if an edge exists at this time instant, wait at the current node in the hope that other links will appear in the future, or move backward in time using an expensive time travel device. A travel that makes use of backward time travel is called a space-time travel. Observe that a backward time travel is necessary to arrive at the destination with zero latency, which is always what we want. Finding an optimal space-time travel is polynomial when the agent knows the entire dynamic graph (including the future edges), even with additional constraints. However, we consider in this paper that the agent discovers the dynamic graph while it is exploring it, in an online manner. In this paper, we propose two models that define how an agent learns new knowledge about the dynamic graph during the execution: the T-online model, where the agent reaching time $t$ learns about the entire past of the network until $t$ (even nodes not yet visited), and the S-online model, where the agent learns about the past and future about the current node he is located. We present an algorithm with an optimal competitive ratio of 2 for the T-online model. In the S-online model, we prove a lower bound of $2/3n-7/4$ and an upper bound of $2n-3$ on the optimal competitive ratio when the cost function is linear. |
| (REG) | Black Hole Search in Dynamic Tori |
| Adri Bhattacharya, Giuseppe Francesco Italiano and Partha Sarathi Mandal | |
| We investigate the black hole search problem by a set of mobile agents in a dynamic torus. Black hole is defined to be a dangerous stationary node which has the capability to destroy any number of incoming agents without leaving any trace of its existence. A torus of size $n\times m$ ($3\leq n \leq m$) is a collection of $n$ row rings and $m$ column rings, and the dynamicity is such that each ring is considered to be 1-interval connected, i.e., in other words at most one edge can be missing from each ring at any round. The parameters which define the efficiency of any black hole search algorithm are: the number of agents and the number of rounds (or \textit{time}) for termination. We consider two initial configurations of mobile agents: first, the agents are co-located and second, the agents are scattered. In each case, we establish lower and upper bounds on the number of agents and on the amount of time required to solve the black hole search problem. |
| (REG) | Gathering in Carrier Graphs: Meeting via Public Transportation System |
| Haozhi Zheng, Ryota Eguchi, Fukuhito Ooshita and Michiko Inoue | |
| The gathering problem requires multiple mobile agents in a network to meet at a single location. This paper investigates the gathering problem in carrier graphs, a subclass of recurrence of edge class of time-varying graphs. By focusing on three subclasses of single carrier graphs - circular, simple, and arbitrary - we clarify the conditions under which the problem can be solved, considering prior knowledge endowed to agents and obtainable online information, such as the count and identifiers of agents or sites. We propose algorithms for solvable cases and analyze the complexities. We also consider general carrier graphs with multiple carriers and propose an algorithm for arbitrary carrier graphs. |
| (REG) | Partial Temporal Vertex Cover with Bounded Activity Intervals |
| Riccardo Dondi, Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli and Alessandra Tappini | |
| Different variants of Vertex Cover have recently garnered attention in the context of temporal graphs. One of these variants is motivated by the need to summarize timeline activities in social networks. Here, the activities of individual vertices, representing users, are characterized by time intervals. In this paper, we explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer ℓ, and the objective is to maximize the number of (temporal) edges that are covered. We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted condition where the temporal domain comprises only two timestamps and each edge appears at most once. Subsequently, we delve into the parameterized complexity of the problem, offering three fixed-parameter algorithms parameterized by: (i) the number k of temporal edges covered by the solution, (ii) the number h of temporal edges not covered by the solution, (iii) the number of vertices n plus the temporal span ℓ. Finally, we present a polynomial-time approximation algorithm achieving a factor of 3/4. |
| (REG) | Forming Large Patterns with Local Robots in the OBLOT Model |
| Christopher Hahn, Jonas Harbig and Peter Kling | |
| In the \emph{arbitrary pattern formation} problem, $n$ autonomous, mobile robots must form an arbitrary pattern $P \subseteq \R^2$. The (deterministic) robots are typically assumed to be indistinguishable, disoriented, and unable to communicate. An important distinction is whether robots have memory and/or a limited viewing range. Previous work managed to form $P$ under a natural symmetry condition if robots have \emph{no memory but an unlimited viewing range}~\cite{DBLP:journals/tcs/YamashitaS10} or if robots have a \emph{limited viewing range but memory}~\cite{DBLP:conf/sirocco/YamauchiY13}. In the latter case, $P$ is only formed in a shrunk version that has constant diameter. Without memory and with limited viewing range, forming arbitrary patterns remains an open problem. We provide a partial solution by showing that $P$ can be formed under the same symmetry condition if the robots' initial diameter is $\leq 1$. Our protocol partitions $P$ into rotation-symmetric components and exploits the initial mutual visibility to form one cluster per component. Using a careful placement of the clusters and their robots, we show that a cluster can move in a coordinated way through its component while \enquote{drawing} $P$ by dropping one robot per pattern coordinate. |
| (REG) | On inefficiently connecting temporal networks |
| Esteban Christiann, Eric Sanlaville and Jason Schoeters | |
| A temporal graph can be represented by a graph with an edge labelling, such that an edge is present in the network if and only if the edge is assigned the corresponding time label. A journey is a labelled path in a temporal graph such that labels on successive edges of the path are increasing, and if all vertices admit journeys to all other vertices, the temporal graph is temporally connected. A temporal spanner is a sublabelling of the temporal graph such that temporal connectivity is maintained. The study of temporal spanners has raised interest since the early 2000’s. Essentially two types of studies have been conducted: the positive side where families of temporal graphs are shown to (deterministically or stochastically) admit sparse temporal spanners, and the negative side where constructions of temporal graphs with no sparse spanners are of importance. Often such studies considered temporal graphs with happy or simple labellings, which associate exactly one label per edge. In this paper, we focus on the negative side and consider proper labellings, where multiple labels per edge are allowed. More precisely, we aim to construct dense temporally connected graphs such that all labels are necessary for temporal connectivity. Our contributions are multiple: we present the first labellings maximizing a local density measure; exact or asymptotically tight results for basic graph families, which are then extended to larger graph families; an extension of an efficient temporal graph labelling generator; and overall denser labellings than previous work even when restricted to happy labellings. |
| (BA) | Collision Detection for Modular Robots -- it is easy to cause collisions and hard to avoid them |
| Siddharth Gupta, Marc van Kreveld, Othon Michail and Andreas Padalkin | |
| We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of deciding whether collisions may occur, or can be avoided, if a set of expansion and contraction operations is executed. We study both discrete- and continuous-time models, and allow operations to be coupled into a single parallel group. Our algorithms to decide if a collision may occur run in $O(n^2\log^2 n)$ time, $O(n^2)$ time, or $O(n\log^2 n)$ time, depending on the presence and type of coupled operations, in a continuous-time model for a modular robot with $n$ nodes. To decide if collisions can be avoided, we show that a very restricted version is already NP-complete in the discrete-time model, while the same problem is polynomial in the continuous-time model. A less restricted version is NP-hard in the continuous-time model. |
| (BA) | Collision-Free Robot Scheduling |
| Duncan Adamson, Nathan Flaherty, Igor Potapov and Paul G. Spirakis | |
| Robots are becoming an increasingly common part of scientific work within laboratory environments. In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for many simple classes of graphs, the problem of determining the fastest schedule, defined by the number of time steps required for a robot to visit every vertex in the schedule and complete every task assigned in its assigned schedule. Explicitly, we provide this result for complete graphs, bipartite graphs, star graphs, and planar graphs. Finally, we provide positive results for line graphs, showing that we can find an optimal set of schedules for $k$ robots completing $m$ tasks of equal length of a path of length $n$ in $O(kmn)$ time, and a $k$-approximation when the length of the tasks is unbounded. |
| (BA) | Crash-tolerant Exploration of Trees by Energy Sharing Mobile Agents |
| Quentin Bramas, Toshimitsu Masuzawa and Sebastien Tixeuil | |
| We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy in two settings: line-shaped graphs, and general trees. |
| (BA) | On the Exponential Growth of Geometric Shapes |
| Nada Almalki, Siddharth Gupta and Othon Michail | |
| In this paper, we explore how geometric structures can be grown exponentially fast. The studied processes start from an initial shape and apply a sequence of centralized growth operations to grow other shapes. We focus on the case where the initial shape is just a single node. A technical challenge in growing shapes that fast is the need to avoid collisions caused when the shape breaks, stretches, or self-intersects. We identify a parameter $k$, representing the number of turning points within specific parts of a shape, and prove that, if edges can only be formed when generating new nodes and cannot be deleted, trees having $O(k)$ turning points on every root-to-leaf path can be grown within $O(k\log n)$ time steps and spirals with $O(\log n)$ turning points can be grown within $O(\log n)$ time steps. For this case, we also show that the maximum number of turning points in a root-to-leaf path of a tree is a lower bound on the number of time steps to grow the tree and that there exists a class of paths such that any path in the class with $\Omega(k)$ turning points requires $\Omega(k\log k)$ time steps to be grown. If nodes can additionally be connected as soon as they become adjacent, we prove that if a shape $S$ has a spanning tree with $O(k)$ turning points on every root-to-leaf path, then the adjacency closure of $S$ can be grown within $O(k \log n)$ time steps. In the strongest model that we study, where edges can be deleted and neighbors can be handed over to newly generated nodes, we obtain a universal algorithm: for any shape $S$ it gives a process that grows $S$ from a single node exponentially fast. |
| (BA) | The Dynamic Steiner Tree problem: definitions, complexity, algorithms |
| Stefan Balev, Yoann Pigné, Eric Sanlaville and Mathilde Vernet | |
| This paper introduces an extension of the Steiner tree problem applied to dynamic graphs. In various application domains of this problem, the associated graphs undergo temporal changes, such as variations in the edge set or associated costs. The paper presents three extension models, and we opt for the one demonstrating the most desirable features: a fixed Steiner set (a set of selected vertices) maintained throughout the time horizon and a minimum cost set of edges ensuring connectivity among the terminal vertices. We show that the resulting problem of minimizing the size of the Steiner set is NP-hard, even when dealing with only two terminals. This contrasts with the corresponding static problem, which is among the rare polynomial versions of the Steiner tree problem. However, polynomial algorithms exist when the size of the Steiner set is bounded. An algorithm is designed, analyzed and tested on specially generated and on real data sets. We show that it solves exactly non trivial instances when the Steiner set size in bounded. |
| (BA) | On the existence of $\delta$-temporal cliques in random simple temporal graphs |
| George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis | |
| We consider random simple temporal graphs in which every edge of the complete graph $K_n$ appears once within the time interval $[0,1]$ independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum $\delta$-clique (namely a clique with edges appearing at most $\delta$ apart within $[0,1]$) in random instances of this model, for any constant~$\delta$. In particular, using the probabilistic method, we prove that the size of a maximum $\delta$-clique is approximately $\frac{2\log{n}}{\log{\frac{1}{\delta}}}$ with high probability (whp).~What seems surprising is that, even though the random simple temporal graph contains $\Theta(n^2)$ overlapping $\delta$-windows, which (when viewed separately) correspond to different random instances of the Erd\H{o}s-R\'{e}nyi random graphs model, the size of the maximum $\delta$-clique in the former model and the maximum clique size of the latter are approximately the same. Furthermore, we show that the minimum interval containing a $\delta$-clique is $\delta-o(\delta)$ whp. We use this result to show that any polynomial time algorithm for \textsc{$\delta$-Temporal Clique} is unlikely to have very large probability of success. |