2026 [ nach oben ]

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphssubmitted to STACS 2026 2026
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair of vertices must be able to reach each other via a time-respecting path. We consider both problems of maximum open tccs (openTCC), which allow temporal paths through vertices outside the component, and closed tccs (closedTCC) which require at least one temporal path entirely within the component for every pair. We focus on the structural parameter of treewidth, tw, and the recently introduced temporal parameter of temporal path number, tpn, which is the minimum number of paths needed to fully describe a temporal graph. We prove that these parameters on their own are not sufficient for fixed parameter tractability: both openTCC and closedTCC are NP-hard even when tw=9, and closedTCC is NP-hard when tpn=6. In contrast, we prove that openTCC is in XP when parameterized by tpn. On the positive side, we show that both problem become fixed parameter tractable under various combinations of structural and temporal parameters that include, tw plus tpn, tw plus the lifetime of the graph, and tw plus the maximum temporal degree.
@preprint{deligkasTemporalComponentsPathGraphs_2025, abstract = {We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair of vertices must be able to reach each other via a time-respecting path. We consider both problems of maximum open tccs (openTCC), which allow temporal paths through vertices outside the component, and closed tccs (closedTCC) which require at least one temporal path entirely within the component for every pair. We focus on the structural parameter of treewidth, tw, and the recently introduced temporal parameter of temporal path number, tpn, which is the minimum number of paths needed to fully describe a temporal graph. We prove that these parameters on their own are not sufficient for fixed parameter tractability: both openTCC and closedTCC are NP-hard even when tw=9, and closedTCC is NP-hard when tpn=6. In contrast, we prove that openTCC is in XP when parameterized by tpn. On the positive side, we show that both problem become fixed parameter tractable under various combinations of structural and temporal parameters that include, tw plus tpn, tw plus the lifetime of the graph, and tw plus the maximum temporal degree.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, booktitle = {submitted to STACS 2026}, keywords = {MSO VCdimension argyriosdeligkas connectedcomponents eduardeiben georgeskretas georgtennigkeit michelledoering parameterizedcomplexity temporalgraphs temporalpathgraph temporalpathumber temporalreachability tigerlilygoldsmith transitivity treewidth year2025}, title = {Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs}, year = 2026 }

2025 [ nach oben ]

Baguley, Samuel; Maus, Yannic Maus; Ruff, Janosch; Skretas, George Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for ColouringInternational Symposium on Theoretical Aspects of Computer Science (STACS) 2025: 13:1–13:20
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from \((2/\sqrt{3})\) to \(4/3\) depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.
@conference{bmrs-stacs25, abstract = {Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from \((2/\sqrt{3})\) to \(4/3\) depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.}, author = {Baguley, Samuel and Maus, Yannic Maus and Ruff, Janosch and Skretas, George}, booktitle = {International Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {georgeskretas janoschruff samuelbaguley stacs year2025}, pages = {13:1-13:20}, title = {Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring}, year = 2025 }

Bals, Ben; Döring, Michelle; Klodt, Nicolas; Skretas, George Dynamic Network Discovery via Infection Tracing 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as rumor spreading in social networks, viral infections, and water contamination. Classical questions include predicting infection behavior in a given network or deducing the network structure from infection data. Most of the research on network infections studies static graphs, that is, the connections in the network are assumed to not change. More recently, temporal graphs, in which connections change over time, have been used to more accurately represent real-world infections, which rarely occur in unchanging networks. We propose a model for temporal graph discovery that is consistent with previous work on static graphs and embraces the greater expressiveness of temporal graphs. For this model, we give algorithms and lower bounds which are often tight. We analyze different variations of the problem, which make our results widely applicable and it also clarifies which aspects of temporal infections make graph discovery easier or harder. We round off our analysis with an experimental evaluation of our algorithm on real-world interaction data from the Stanford Network Analysis Project and on temporal Erdős-Renyi graphs. On Erdős-Renyi graphs, we uncover a threshold behavior, which can be explained by a novel connectivity parameter that we introduce during our theoretical analysis.
@inproceedings{bals_DynamicNetwork_2025, abstract = {Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as rumor spreading in social networks, viral infections, and water contamination. Classical questions include predicting infection behavior in a given network or deducing the network structure from infection data. Most of the research on network infections studies static graphs, that is, the connections in the network are assumed to not change. More recently, temporal graphs, in which connections change over time, have been used to more accurately represent real-world infections, which rarely occur in unchanging networks. We propose a model for temporal graph discovery that is consistent with previous work on static graphs and embraces the greater expressiveness of temporal graphs. For this model, we give algorithms and lower bounds which are often tight. We analyze different variations of the problem, which make our results widely applicable and it also clarifies which aspects of temporal infections make graph discovery easier or harder. We round off our analysis with an experimental evaluation of our algorithm on real-world interaction data from the Stanford Network Analysis Project and on temporal Erdős-Renyi graphs. On Erdős-Renyi graphs, we uncover a threshold behavior, which can be explained by a novel connectivity parameter that we introduce during our theoretical analysis.}, author = {Bals, Ben and Döring, Michelle and Klodt, Nicolas and Skretas, George}, keywords = {benbals georgeskretas ijcai masterthesis michelledoering networkdiscovery nicolasklodt random spreadingprocess temporalgraphs year2025}, title = {Dynamic Network Discovery via Infection Tracing}, year = 2025 }

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsProceedings of the AAAI Conference on Artificial Intelligence 2025: 26498–26506
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{deligkas_HowMany_2025, abstract = {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.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, keywords = {aaai argyriosdeligkas eduardeiben exactedge-cover georgeskretas georgtennigkeit michelledoering parameterizedcomplexity pathcover reachability temporalgraphs temporalpathgraph temporalpathumber tigerlilygoldsmith year2025}, month = {Apr.}, number = 25, pages = {26498-26506}, title = {How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs}, volume = 39, year = 2025 }

Bals, Ben; Döring, Michelle; Klodt, Nicolas; Skretas, George Catch Me If You Can: Finding the Source of Infections in Temporal Networks 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Source detection (SD) is the task of finding the origin of a spreading process in a network. Algorithms for SD help us combat diseases, misinformation, pollution, and more, and have been studied by physicians, physicists, sociologists, and computer scientists. The field has received considerable attention and been analyzed in many settings (e.g., under different models of spreading processes), yet all previous work shares the same assumption that the network the spreading process takes place in has the same structure at every point in time. For example, if we consider how a disease spreads through a population, it is unrealistic to assume that two people can either never or at every time infect each other, rather such an infection is possible precisely when they meet. Therefore, we propose an extended model of SD based on temporal graphs, where each link between two nodes is only present at some time step. Temporal graphs have become a standard model of time-varying graphs, and, recently, researchers have begun to study infection problems (such as influence maximization) on temporal graphs (arXiv:2303.11703, [Gayraud et al., 2015]). We give the first formalization of SD on temporal graphs. For this, we employ the standard SIR model of spreading processes ([Hethcote, 1989]). We give both lower bounds and algorithms for the SD problem in a number of different settings, such as with consistent or dynamic source behavior and on general graphs as well as on trees.
@preprint{bals_CatchMe_2025, abstract = {Source detection (SD) is the task of finding the origin of a spreading process in a network. Algorithms for SD help us combat diseases, misinformation, pollution, and more, and have been studied by physicians, physicists, sociologists, and computer scientists. The field has received considerable attention and been analyzed in many settings (e.g., under different models of spreading processes), yet all previous work shares the same assumption that the network the spreading process takes place in has the same structure at every point in time. For example, if we consider how a disease spreads through a population, it is unrealistic to assume that two people can either never or at every time infect each other, rather such an infection is possible precisely when they meet. Therefore, we propose an extended model of SD based on temporal graphs, where each link between two nodes is only present at some time step. Temporal graphs have become a standard model of time-varying graphs, and, recently, researchers have begun to study infection problems (such as influence maximization) on temporal graphs (arXiv:2303.11703, [Gayraud et al., 2015]). We give the first formalization of SD on temporal graphs. For this, we employ the standard SIR model of spreading processes ([Hethcote, 1989]). We give both lower bounds and algorithms for the SD problem in a number of different settings, such as with consistent or dynamic source behavior and on general graphs as well as on trees.}, author = {Bals, Ben and Döring, Michelle and Klodt, Nicolas and Skretas, George}, keywords = {benbals georgeskretas masterthesis michelledoering nicolasklodt random sourcedetection spreadingprocess temporalgraphs year2025}, title = {Catch Me If You Can: Finding the Source of Infections in Temporal Networks}, year = 2025 }

2024 [ nach oben ]

Angrick, Sebastian; Bals, Ben; Friedrich, Tobias; Gawendowicz, Hans; Hastrich, Niko; Klodt, Nicolas; Lenzner, Pascal; Schmidt, Jonas; Skretas, George; Wells, Armin How to Reduce Temporal Cliques to Find Sparse SpannersEuropean Symposium on Algorithms (ESA) 2024
[ BibTeX ]
 
@inproceedings{angrick2024reduce, author = {Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa georgeskretas hansgawendowicz nicolasklodt pascallenzner tobiasfriedrich year2024}, title = {How to Reduce Temporal Cliques to Find Sparse Spanners}, year = 2024 }

2023 [ nach oben ]

Deligkas, Argyrios; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed SourceAutonomous Agents and Multi-Agent Systems (AAMAS) 2023: 2222–2230
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions.In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.
@inproceedings{deligkas2023being, abstract = {We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions.In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.}, author = {Deligkas, Argyrios and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {sys:relevantfor:ae aamas georgeskretas michelledoering year2023}, pages = {2222–2230}, title = {Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source}, year = 2023 }

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Gawendowicz, Hans; Klodt, Nicolas; Lenzner, Pascal; Skretas, George Temporal Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 2511–2519
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{bilo2023temporal, abstract = {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.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Gawendowicz, Hans and Klodt, Nicolas and Lenzner, Pascal and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {georgeskretas hansgawendowicz ijcai nicolasklodt pascallenzner sarelcohen tobiasfriedrich year2023}, pages = {2511–2519}, title = {Temporal Network Creation Games}, year = 2023 }

Deligkas, Argyrios; Eiben, Eduard; Skretas, George Minimizing Reachability Times on Temporal Graphs via Shifting LabelsInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 5333–5340
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.
@inproceedings{deligkas2023minimizing, abstract = {We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.}, author = {Deligkas, Argyrios and Eiben, Eduard and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {sys:relevantfor:ae georgeskretas ijcai myown year2023}, pages = {5333–5340}, title = {Minimizing Reachability Times on Temporal Graphs via Shifting Labels}, year = 2023 }

2022 [ nach oben ]

Mertzios, George B; Michail, Othon; Skretas, George; Spirakis, Paul G.; Theofilatos, Michail The Complexity of Growing a GraphInternational Symposium on Algorithms and Experiments for Wireless Sensor Networks 2022: 123–137
[ BibTeX ] [ DOI ] [ Download ]
 
@inproceedings{mertzios2022complexity, author = {Mertzios, George B and Michail, Othon and Skretas, George and Spirakis, Paul G. and Theofilatos, Michail}, booktitle = {International Symposium on Algorithms and Experiments for Wireless Sensor Networks}, keywords = {sys:relevantfor:ae georgeskretas myown year2022}, pages = {123-137}, publisher = {Springer}, title = {The Complexity of Growing a Graph}, year = 2022 }

2021 [ nach oben ]

Michail, Othon; Skretas, George; Spirakis, Paul G. Distributed computation and reconfiguration in actively dynamic networksDistributed Computing 2021: 185–206
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@article{michail2022distributed, author = {Michail, Othon and Skretas, George and Spirakis, Paul G.}, journal = {Distributed Computing}, keywords = {sys:relevantfor:ae distributed dynamic georgeskretas reconfiguration}, month = {dec}, pages = {185-206}, title = {Distributed computation and reconfiguration in actively dynamic networks}, volume = 35, year = 2021 }

2020 [ nach oben ]

Michail, Othon; Skretas, George; Spirakis, G. Paul Distributed Computation and Reconfiguration in Actively Dynamic NetworksPrinciples of Distributed Computing (PODC) 2020: 448–457
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper, motivated by recent advances in the algorithmic theory of dynamic networks, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network \(G_s\) to a target network \(G_f\) from a family of networks having some good properties, like small diameter. With reasonably powerful computational entities, there is a straightforward algorithm that transforms any \(G_s\) into a spanning clique in \( \mathcal{O} (\log n) \) time, where time is measured in synchronous rounds and n is the number of entities. From the clique, the algorithm can then compute any global function on inputs and reconfigure to any desired target network in one additional round. We argue that such a strategy, while time-optimal, is impractical for real applications. In real dynamic networks there is typically a cost associated with creating and maintaining connections. To formally capture such costs, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. The clique formation strategy highlighted above, maximizes all of them. We aim at improved algorithms that will achieve (poly)\(log(n)\) time while minimizing the edge-complexity for the general task of transforming any \(G_s\) into a \(G_f\) of diameter (poly)\(\log(n)\). There is a natural trade-off between time and edge complexity. Our main lower bound shows that \(\Omega(n)\) total edge activations and \(\Omega(n/\log n)\) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of \(\Theta(\log n)\) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in \(\mathcal{O}(log n)\) time, with at most \(2n\) active edges per round, an optimal total of \(\mathcal{O}(n \log n)\) edge activations, a maximum degree \(n −1\), and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations, that is, \(\mathcal{O}(\log^2 n)\) and \(\mathcal{O}(n \log^2 n)\), respectively. It gives a target network of diameter \(\mathcal{O}(\log n)\) and uses \(\mathcal{O}(n)\) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of \(\mathcal{o}(\log^2 n)\). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms may open new avenues for research in the algorithmic theory of dynamic networks. At the same time, they may serve as an abstraction of more constrained active-reconfiguration systems, such as reconfigurable robotics which come with geometric constraints, and draw interesting connections with alternative network reconfiguration models, like overlay network construction and network constructors. We discuss several open problems and promising future research directions.
@inproceedings{michail2020distributed, abstract = {In this paper, motivated by recent advances in the algorithmic theory of dynamic networks, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network \(G_s\) to a target network \(G_f\) from a family of networks having some good properties, like small diameter. With reasonably powerful computational entities, there is a straightforward algorithm that transforms any \(G_s\) into a spanning clique in \( \mathcal{O} (\log n) \) time, where time is measured in synchronous rounds and n is the number of entities. From the clique, the algorithm can then compute any global function on inputs and reconfigure to any desired target network in one additional round. We argue that such a strategy, while time-optimal, is impractical for real applications. In real dynamic networks there is typically a cost associated with creating and maintaining connections. To formally capture such costs, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. The clique formation strategy highlighted above, maximizes all of them. We aim at improved algorithms that will achieve (poly)\(log(n)\) time while minimizing the edge-complexity for the general task of transforming any \(G_s\) into a \(G_f\) of diameter (poly)\(\log(n)\). There is a natural trade-off between time and edge complexity. Our main lower bound shows that \(\Omega(n)\) total edge activations and \(\Omega(n/\log n)\) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of \(\Theta(\log n)\) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in \(\mathcal{O}(log n)\) time, with at most \(2n\) active edges per round, an optimal total of \(\mathcal{O}(n \log n)\) edge activations, a maximum degree \(n −1\), and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations, that is, \(\mathcal{O}(\log^2 n)\) and \(\mathcal{O}(n \log^2 n)\), respectively. It gives a target network of diameter \(\mathcal{O}(\log n)\) and uses \(\mathcal{O}(n)\) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of \(\mathcal{o}(\log^2 n)\). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms may open new avenues for research in the algorithmic theory of dynamic networks. At the same time, they may serve as an abstraction of more constrained active-reconfiguration systems, such as reconfigurable robotics which come with geometric constraints, and draw interesting connections with alternative network reconfiguration models, like overlay network construction and network constructors. We discuss several open problems and promising future research directions.}, author = {Michail, Othon and Skretas, George and Spirakis, G. Paul}, booktitle = {Principles of Distributed Computing (PODC)}, keywords = {sys:relevantfor:ae georgeskretas michailothon paulgspirakis podc year2020}, pages = {448–457}, title = {Distributed Computation and Reconfiguration in Actively Dynamic Networks}, year = 2020 }

2019 [ nach oben ]

Michail, Othon; Skretas, George; Spirakis, G. Paul On the transformation capability of feasible mechanisms for programmable matterComputer and System Sciences 2019: 18–39
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this work, we study theoretical models of 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): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on 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 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 PSPACE and study the problem of determining the minimum 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 number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is \(\Theta(n^2)\). We improve this to \( \mathcal{O}(n) \) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next 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 transformation.
@article{michail2019transformation, abstract = {In this work, we study theoretical models of 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): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on 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 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 PSPACE and study the problem of determining the minimum 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 number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is \(\Theta(n^2)\). We improve this to \( \mathcal{O}(n) \) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next 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 transformation.}, author = {Michail, Othon and Skretas, George and Spirakis, G. Paul}, journal = {Computer and System Sciences}, keywords = {sys:relevantfor:ae georgeskretas jcss michailothon paulgspirakis year2019}, pages = {18–39}, title = {On the transformation capability of feasible mechanisms for programmable matter}, year = 2019 }

2017 [ nach oben ]

Michail, Othon; Skretas, George; Spirakis, G. Paul On the Transformation Capability of Feasible Mechanisms for Programmable MatterInternational Colloquium on Automata, Languages and Programming (ICALP) 2017: 136:1–136:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this work, we study theoretical models of 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): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on 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 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 PSPACE and study the problem of determining the minimum 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 number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is \(\Theta(n^2)\). We improve this to \( \mathcal{O}(n) \) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next 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 transformation.
@inproceedings{michail2017transformation, abstract = {In this work, we study theoretical models of 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): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on 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 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 PSPACE and study the problem of determining the minimum 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 number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is \(\Theta(n^2)\). We improve this to \( \mathcal{O}(n) \) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next 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 transformation.}, author = {Michail, Othon and Skretas, George and Spirakis, G. Paul}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sys:relevantfor:ae georgeskretas icalp michailothon paulgspirakis year2017}, pages = {136:1–136:15}, title = {On the Transformation Capability of Feasible Mechanisms for Programmable Matter}, year = 2017 }