GSGeorge Skretas

George Skretas

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


George Skretas has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Temporal network creation games: the impact of non-locality and terminals

    by Davide Bilò, Sarel Cohen, Tobias Friedrich, Hans Gawendowicz, Nicolas Klodt, Pascal Lenzner, George Skretas

    Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting , and agents might only want to ensure reachability of a subset of nodes, called the terminal model . For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.

  • Open Access

    Dynamic Network Discovery via Infection Tracing

    by Ben Bals, Michelle Döring, Nicolas Klodt, George Skretas

    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.

  • Open Access

    Temporal Exploration of Random Spanning Tree Models

    by Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, Viktor Zamaraev

    The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs $(G_i)_{i\in \mathbb{N}}$ on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the $i$-th step uses an edge from $G_i$. If each such $G_i$ is connected, then an exploration of length $n^2$ exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore. Motivated by this limited understanding and the central role of the Temporal Graph Exploration problem in temporal graph theory, we study the problem in a randomised setting. We introduce the Random Spanning Tree (RST) model, which consists of a set of $n$-vertex trees together with an arbitrary probability distribution $μ$ over this set. A random temporal graph generated by the RST model is a sequence of independent samples drawn from $μ$. We initiate a systematic study of the Temporal Graph Exploration problem in such random temporal graphs and establish tight general bounds on exploration time. Our first main result proves that any RST model can, with high probability (w.h.p.), be explored in $O(n^{3/2})$ time, and we show that this bound is tight up to a constant factor. This demonstrates a fundamental difference between the adversarial and random settings. Our second main result shows that if all trees of an RST are subgraphs of a fixed graph with $m$ edges then, w.h.p.\ , it can be explored in $O(m)$ time.

  • Open Access

    How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs

    by Argyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith, George Skretas, Georg Tennigkeit

    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.


  • Open Access

    Temporal Network Creation Games: The Impact of Non-Locality and Terminals

    by Davide Bilò, Sarel Cohen, Tobias Friedrich, Hans Gawendowicz, Nicolas Klodt, Pascal Lenzner, George Skretas

    We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks.


  • Open Access

    The complexity of growing a graph

    by George Mertzios, Othon Michail, George Skretas, Paul G. Spirakis, Michail Theofilatos


  • Open Access

    How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs

    by Argyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith, George Skretas, Georg Tennigkeit

    Logistics and transportation networks require a large amount of resources to realize 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 realize 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 or not. We almost completely resolve the complexity of all these problems and provide dichotomies for each one of them with respect to k.

  • Open Access

    Minimizing Reachability Times on Temporal Graphs via Shifting Labels

    by Argyrios Deligkas, Eduard Eiben, George Skretas

    We study how we can accelerate the spreading of information in temporal graphs via shifting 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, shifting some connections, i.e., advancing or delaying them, can decrease the time required to reach from some vertex (source) to another vertex. We study how we can minimize the maximum time a set of sources needs to reach every vertex, when we are allowed to shift some of the connections. If we restrict the allowed number of changes, we prove that, already for a single source, the problem is NP-hard, and W[2]-hard when parameterized by the number of changes. Then we focus on unconstrained number of changes. We derive a polynomial-time algorithm when there is one source. When there are two sources, we show that the problem becomes NP-hard; on the other hand, we design an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution, that works for any number of sources. Finally, we provide polynomial-time algorithms for several graph classes.


  • Open Access

    Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source

    by Argyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith, George Skretas

    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 four 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. In the MaxViralTstep objective, the goal is to maximize the number of vertices that are infected at a given time step. Finally, in MinNonViralTime, the goal is to maximize the total number of vertices that get infected every $d$ time steps. We perform a thorough complexity theoretic analysis for these four 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.