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 }