Search Results

Documents authored by Spirakis, Paul

Found 2 Possible Name Variants:

Spirakis, Paul G.

Document
DOI: 10.4230/LIPIcs.SAND.2024.16
Temporal Graph Realization from Fastest Paths

Authors: Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
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 × n matrix D and a Δ ∈ ℕ, the goal is to construct a Δ-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. [Erdős 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.
Cite as

Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. Temporal Graph Realization from Fastest Paths. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.SAND.2024.16,
  author =	{Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.},
  title =	{{Temporal Graph Realization from Fastest Paths}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.16},
  URN =		{urn:nbn:de:0030-drops-198945},
  doi =		{10.4230/LIPIcs.SAND.2024.16},
  annote =	{Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, parameterized complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.22
Brief Announcement: Collision-Free Robot Scheduling

Authors: Duncan Adamson, Nathan Flaherty, Igor Potapov, and Paul G. Spirakis

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
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, or traverse the same edge, at the same time. 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 the problem of finding a task-fulfilling schedule in at most L timesteps is NP-complete for many simple classes of graphs. 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.
Cite as

Duncan Adamson, Nathan Flaherty, Igor Potapov, and Paul G. Spirakis. Brief Announcement: Collision-Free Robot Scheduling. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 22:1-22:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{adamson_et_al:LIPIcs.SAND.2024.22,
  author =	{Adamson, Duncan and Flaherty, Nathan and Potapov, Igor and Spirakis, Paul G.},
  title =	{{Brief Announcement: Collision-Free Robot Scheduling}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{22:1--22:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.22},
  URN =		{urn:nbn:de:0030-drops-199004},
  doi =		{10.4230/LIPIcs.SAND.2024.22},
  annote =	{Keywords: Graph Exploration, Scheduling, NP-Completeness, Approximation Algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.27
Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs

Authors: George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
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 δ-clique (namely a clique with edges appearing at most δ apart within [0,1]) in random instances of this model, for any constant δ. In particular, using the probabilistic method, we prove that the size of a maximum δ-clique is approximately (2 log n)/(log 1/δ) with high probability (whp). What seems surprising is that, even though the random simple temporal graph contains Θ(n²) overlapping δ-windows, which (when viewed separately) correspond to different random instances of the Erdős-Rényi random graphs model, the size of the maximum δ-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 δ-clique is δ-o(δ) whp. We use this result to show that any polynomial time algorithm for δ-Temporal Clique is unlikely to have very large probability of success.
Cite as

George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 27:1-27:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.SAND.2024.27,
  author =	{Mertzios, George B. and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul G.},
  title =	{{Brief Announcement: On the Existence of \delta-Temporal Cliques in Random Simple Temporal Graphs}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{27:1--27:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.27},
  URN =		{urn:nbn:de:0030-drops-199056},
  doi =		{10.4230/LIPIcs.SAND.2024.27},
  annote =	{Keywords: Simple random temporal graph, \delta-temporal clique, probabilistic method}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.5
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

Authors: Nina Klobas, George B. Mertzios, and Paul G. Spirakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Graphs are fundamental tools for modelling relations among objects in various scientific fields. However, traditional static graphs have limitations when it comes to capturing the dynamic nature of real-world systems. To overcome this limitation, temporal graphs have been introduced as a framework to model graphs that change over time. In temporal graphs the edges among vertices appear and disappear at specific time steps, reflecting the temporal dynamics of the observed system, which allows us to analyse time dependent patterns and processes. In this paper we focus on the research related to sliding time windows in temporal graphs. Sliding time windows offer a way to analyse specific time intervals within the lifespan of a temporal graph. By sliding the window along the timeline, we can examine the graph’s characteristics and properties within different time periods. This paper provides an overview of the research on sliding time windows in temporal graphs. Although progress has been made in this field, there are still many interesting questions and challenges to be explored. We discuss some of the open problems and highlight their potential for future research.
Cite as

Nina Klobas, George B. Mertzios, and Paul G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2023.5,
  author =	{Klobas, Nina and Mertzios, George B. and Spirakis, Paul G.},
  title =	{{Sliding into the Future: Investigating Sliding Windows in Temporal Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-185397},
  doi =		{10.4230/LIPIcs.MFCS.2023.5},
  annote =	{Keywords: Temporal Graphs, Sliding Time Windows}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.33
New Clocks, Optimal Line Formation and Self-Replication Population Protocols

Authors: Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In this paper we consider a known variant of the standard population protocol model in which agents are allowed to be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time. The main focus of this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. - We propose and analyze a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guarantees in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n). - We prove that any spanning line formation protocol requires Ω(nlog n) parallel time if high probability guaranty is imposed. We also show that the new clock enables an optimal O(nlog n) parallel time spanning line construction, which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are limited to the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart. - We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The bit pipelining mechanism and the time complexity analysis of self-replication process mimic those used in the probabilistic bubble-sort argument. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in parallel in time O(n(k+log n)log l). We also discuss application of the strand self-replication protocol to pattern matching. All protocols are always correct and provide time guarantees with high probability defined as 1-n^(-η), for a constant η > 0.
Cite as

Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak. New Clocks, Optimal Line Formation and Self-Replication Population Protocols. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.STACS.2023.33,
  author =	{G\k{a}sieniec, Leszek and Spirakis, Paul G. and Stachowiak, Grzegorz},
  title =	{{New Clocks, Optimal Line Formation and Self-Replication Population Protocols}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.33},
  URN =		{urn:nbn:de:0030-drops-176857},
  doi =		{10.4230/LIPIcs.STACS.2023.33},
  annote =	{Keywords: Population protocols, constructors, probabilistic bubble-sort, self-replication}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.62
The Complexity of Computing Optimum Labelings for Temporal Connectivity

Authors: Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number |λ| of time-labels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number |R| of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number |R| of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).
Cite as

Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The Complexity of Computing Optimum Labelings for Temporal Connectivity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2022.62,
  author =	{Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.},
  title =	{{The Complexity of Computing Optimum Labelings for Temporal Connectivity}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.62},
  URN =		{urn:nbn:de:0030-drops-168603},
  doi =		{10.4230/LIPIcs.MFCS.2022.62},
  annote =	{Keywords: Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SAND.2022.2
Algorithmic Problems on Temporal Graphs (Invited Talk)

Authors: Paul G. Spirakis

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Research on Temporal Graphs has expanded in the last few years. Most of the results till now, address problems related to the notion of Temporal Paths (and Temporal Connectivity). In this talk, we focus, instead, on problems whose main topic is not on Temporal Paths. In particular, we will discuss Temporal Vertex Covers, the notion of Temporal Transitivity, and also issues and models of stochastic temporal graphs. We believe that several algorithmic graph problems, not directly related to paths, can be raised in the temporal domain. This may motivate new research towards lifting more topics of algorithmic graph theory to the temporal case.
Cite as

Paul G. Spirakis. Algorithmic Problems on Temporal Graphs (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{spirakis:LIPIcs.SAND.2022.2,
  author =	{Spirakis, Paul G.},
  title =	{{Algorithmic Problems on Temporal Graphs}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.2},
  URN =		{urn:nbn:de:0030-drops-159446},
  doi =		{10.4230/LIPIcs.SAND.2022.2},
  annote =	{Keywords: Temporal graph, stochastic temporal graph, vertex cover, temporal transitivity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.75
The Complexity of Transitively Orienting Temporal Graphs

Authors: George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.
Cite as

George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp},
  title =	{{The Complexity of Transitively Orienting Temporal Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.75},
  URN =		{urn:nbn:de:0030-drops-145157},
  doi =		{10.4230/LIPIcs.MFCS.2021.75},
  annote =	{Keywords: Temporal graph, transitive orientation, transitive closure, polynomial-time algorithm, NP-hardness, satisfiability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.27
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Authors: Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0.299862744n) = O(1.23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0.3n) = O(1.2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0.2971925n) = O(1.22876ⁿ). Our algorithm is based on a fundamental structural property of Thomason’s lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ,Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.
Cite as

Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.MFCS.2020.27,
  author =	{Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G. and Zamaraev, Viktor},
  title =	{{Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.27},
  URN =		{urn:nbn:de:0030-drops-126953},
  doi =		{10.4230/LIPIcs.MFCS.2020.27},
  annote =	{Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.21
Crystal Structure Prediction via Oblivious Local Search

Authors: Dmytro Antypov, Argyrios Deligkas, Vladimir Gusev, Matthew J. Rosseinsky, Paul G. Spirakis, and Michail Theofilatos

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand, usually easy to implement, but they can be slow in practice. On the other hand, the more sophisticated approaches perform well in general, however almost all of them have a large number of parameters that require fine tuning and, in the majority of the cases, chemical expertise is needed in order to properly set them up. In addition, due to the chemical expertise involved in the parameter-tuning, these approaches can be biased towards previously-known crystal structures. Our contribution is twofold. Firstly, we formalize the Crystal Structure Prediction problem, alongside several other intermediate problems, from a theoretical computer science perspective. Secondly, we propose an oblivious algorithm for Crystal Structure Prediction that is based on local search. Oblivious means that our algorithm requires minimal knowledge about the composition we are trying to compute a crystal structure for. In addition, our algorithm can be used as an intermediate step by any method. Our experiments show that our algorithms outperform the standard basin hopping, a well studied algorithm for the problem.
Cite as

Dmytro Antypov, Argyrios Deligkas, Vladimir Gusev, Matthew J. Rosseinsky, Paul G. Spirakis, and Michail Theofilatos. Crystal Structure Prediction via Oblivious Local Search. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{antypov_et_al:LIPIcs.SEA.2020.21,
  author =	{Antypov, Dmytro and Deligkas, Argyrios and Gusev, Vladimir and Rosseinsky, Matthew J. and Spirakis, Paul G. and Theofilatos, Michail},
  title =	{{Crystal Structure Prediction via Oblivious Local Search}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.21},
  URN =		{urn:nbn:de:0030-drops-120950},
  doi =		{10.4230/LIPIcs.SEA.2020.21},
  annote =	{Keywords: crystal structure prediction, local search, combinatorial neighborhood}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.131
How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?

Authors: Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis, and Viktor Zamaraev

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a sequence of snapshots {G_t=(V,E_t) subseteq G: t in N}, one for each time step t >= 1. In this paper we study stochastic temporal graphs, i.e. stochastic processes G={G_t subseteq G: t in N} whose random variables are the snapshots of a temporal graph on G. A natural feature of stochastic temporal graphs which can be observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; that is, the probability an edge e in E appears at time step t depends on its appearance (or absence) at the previous k steps. In this paper we study the hierarchy of models memory-k, k >= 0, which address this memory effect in an edge-centric network evolution: every edge of G has its own probability distribution for its appearance over time, independently of all other edges. Clearly, for every k >= 1, memory-(k-1) is a special case of memory-k. However, in this paper we make a clear distinction between the values k=0 ("no memory") and k >= 1 ("some memory"), as in some cases these models exhibit a fundamentally different computational behavior for these values of k, as our results indicate. For every k >= 0 we investigate the computational complexity of two naturally related, but fundamentally different, temporal path (or journey) problems: {Minimum Arrival} and {Best Policy}. In the first problem we are looking for the expected arrival time of a foremost journey between two designated vertices {s},{y}. In the second one we are looking for the expected arrival time of the best policy for actually choosing a particular {s}-{y} journey. We present a detailed investigation of the computational landscape of both problems for the different values of memory k. Among other results we prove that, surprisingly, {Minimum Arrival} is strictly harder than {Best Policy}; in fact, for k=0, {Minimum Arrival} is #P-hard while {Best Policy} is solvable in O(n^2) time.
Cite as

Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis, and Viktor Zamaraev. How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akrida_et_al:LIPIcs.ICALP.2019.131,
  author =	{Akrida, Eleni C. and Mertzios, George B. and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul G. and Zamaraev, Viktor},
  title =	{{How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{131:1--131:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.131},
  URN =		{urn:nbn:de:0030-drops-107071},
  doi =		{10.4230/LIPIcs.ICALP.2019.131},
  annote =	{Keywords: Temporal network, stochastic temporal graph, temporal path, #P-hard problem, polynomial-time approximation scheme}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.138
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Authors: Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete [Filos-Ratsikas and Goldberg, 2018; Filos-Ratsikas and Goldberg, 2018], we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP-hard, and deciding whether there exists a solution with fewer than n cuts is ETR-complete. We also give a QPTAS for the case where each agent’s valuation is a polynomial. Along the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP subseteq BU subseteq TFETR and that LinearBU = PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.
Cite as

Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.ICALP.2019.138,
  author =	{Deligkas, Argyrios and Fearnley, John and Melissourgos, Themistoklis and Spirakis, Paul G.},
  title =	{{Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{138:1--138:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.138},
  URN =		{urn:nbn:de:0030-drops-107141},
  doi =		{10.4230/LIPIcs.ICALP.2019.138},
  annote =	{Keywords: PPA, FIXP, ETR, consensus halving, circuit, reduction, complexity class}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.46
Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time

Authors: David Doty, Mahsa Eftekhari, Othon Michail, Paul G. Spirakis, and Michail Theofilatos

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n^60) states (O(1) + 60 log n bits of memory per agent) with probability 1-O((log log n)/n). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with omega(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.
Cite as

David Doty, Mahsa Eftekhari, Othon Michail, Paul G. Spirakis, and Michail Theofilatos. Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.DISC.2018.46,
  author =	{Doty, David and Eftekhari, Mahsa and Michail, Othon and Spirakis, Paul G. and Theofilatos, Michail},
  title =	{{Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{46:1--46:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.46},
  URN =		{urn:nbn:de:0030-drops-98359},
  doi =		{10.4230/LIPIcs.DISC.2018.46},
  annote =	{Keywords: population protocol, counting, leader election, polylogarithmic time}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.148
Temporal Vertex Cover with a Sliding Time Window

Authors: Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of G, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can only be covered by one of its endpoints at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number Delta, and our aim is to cover every edge at least once at every Delta consecutive time steps. In both cases we wish to minimize the total number of "vertex appearances" that are needed to cover the whole graph. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.
Cite as

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal Vertex Cover with a Sliding Time Window. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 148:1-148:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akrida_et_al:LIPIcs.ICALP.2018.148,
  author =	{Akrida, Eleni C. and Mertzios, George B. and Spirakis, Paul G. and Zamaraev, Viktor},
  title =	{{Temporal Vertex Cover with a Sliding Time Window}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{148:1--148:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.148},
  URN =		{urn:nbn:de:0030-drops-91522},
  doi =		{10.4230/LIPIcs.ICALP.2018.148},
  annote =	{Keywords: Temporal networks, temporal vertex cover, APX-hard, approximation algorithm, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.150
The Price of Stability of Weighted Congestion Games

Authors: George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Omega(Phi_d)^{d+1}, where Phi_d ~ d/ln d is the unique positive root of equation x^{d+1}=(x+1)^d. This essentially closes the huge gap between Theta(d) and Phi_d^{d+1} and asymptotically matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Omega((1+1/alpha)^d/d) on the PoS of alpha-approximate Nash equilibria, even for singleton games. All our lower bounds extend to network congestion games, and hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of alpha-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter alpha. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from Theta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of alpha-approximate Nash equilibria is at most (d+1)/alpha.
Cite as

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The Price of Stability of Weighted Congestion Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 150:1-150:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2018.150,
  author =	{Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Spirakis, Paul G.},
  title =	{{The Price of Stability of Weighted Congestion Games}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{150:1--150:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.150},
  URN =		{urn:nbn:de:0030-drops-91541},
  doi =		{10.4230/LIPIcs.ICALP.2018.150},
  annote =	{Keywords: Congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.20
Binary Search in Graphs Revisited

Authors: Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al., STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex– the "median"–which minimises a potential \Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential \Gamma that allows querying approximate medians.
Cite as

Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis. Binary Search in Graphs Revisited. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.MFCS.2017.20,
  author =	{Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G.},
  title =	{{Binary Search in Graphs Revisited}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.20},
  URN =		{urn:nbn:de:0030-drops-80589},
  doi =		{10.4230/LIPIcs.MFCS.2017.20},
  annote =	{Keywords: binary search, graph, approximate query, probabilistic algorithm, lower bound.}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.136
On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Authors: Othon Michail, George Skretas, and Paul G. Spirakis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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 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.
Cite as

Othon Michail, George Skretas, and Paul G. Spirakis. On the Transformation Capability of Feasible Mechanisms for Programmable Matter. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 136:1-136:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{michail_et_al:LIPIcs.ICALP.2017.136,
  author =	{Michail, Othon and Skretas, George and Spirakis, Paul G.},
  title =	{{On the Transformation Capability of Feasible Mechanisms for Programmable Matter}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{136:1--136:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.136},
  URN =		{urn:nbn:de:0030-drops-74341},
  doi =		{10.4230/LIPIcs.ICALP.2017.136},
  annote =	{Keywords: programmable matter, transformation, reconfigurable robotics, shape formation, complexity, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.14
Deterministic Population Protocols for Exact Majority and Plurality

Authors: Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours. The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.
Cite as

Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.OPODIS.2016.14,
  author =	{Gasieniec, Leszek and Hamilton, David and Martin, Russell and Spirakis, Paul G. and Stachowiak, Grzegorz},
  title =	{{Deterministic Population Protocols for Exact Majority and Plurality}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.14},
  URN =		{urn:nbn:de:0030-drops-70837},
  doi =		{10.4230/LIPIcs.OPODIS.2016.14},
  annote =	{Keywords: Deterministic population protocols, majority, plurality consenus}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.68
Stably Computing Order Statistics with Arithmetic Population Protocols

Authors: George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Population Protocol (APP) model, embarking from the well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In the APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of the size of the population), each of which can store an element from a totally ordered set S of samples. Whenever two agents interact with each other, they update their states and the values stored in their registers according to a joint transition function. This transition function is also restricted; it only allows (a) comparisons and (b) copy / paste operations for the sample values that are stored in the registers of the two interacting agents. Agents can only meet in pairs via a fair scheduler and are required to eventually converge to the same output value of the function that the protocol globally and stably computes. We present two different APPs for stably computing the median of the input values, initially stored on the agents of the population. Our first APP, in which every agent has 3 registers and no states, stably computes (with probability 1) the median under any fair scheduler in any strongly connected directed (or connected undirected) interaction graph. Under the probabilistic scheduler, we show that our protocol stably computes the median in O(n^6) number of interactions in a connected undirected interaction graph of n agents. Our second APP, in which every agent has 2 registers and O(n^2 log{n}) states, computes to the correct median of the input with high probability in O(n^3 log{n}) interactions, assuming the probabilistic scheduler and the complete interaction graph. Finally we present a third APP which, for any k, stably computes the k-th smallest element of the input of the population under any fair scheduler and in any strongly connected directed (or connected undirected) interaction graph. In this APP every agent has 2 registers and n states. Upon convergence every agent has a different state; all these states provide a total ordering of the agents with respect to their input values.
Cite as

George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Stably Computing Order Statistics with Arithmetic Population Protocols. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2016.68,
  author =	{Mertzios, George B. and Nikoletseas, Sotiris E. and Raptopoulos, Christoforos L. and Spirakis, Paul G.},
  title =	{{Stably Computing Order Statistics with Arithmetic Population Protocols}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.68},
  URN =		{urn:nbn:de:0030-drops-64805},
  doi =		{10.4230/LIPIcs.MFCS.2016.68},
  annote =	{Keywords: arithmetic population protocols, order statistics, median, k-minimum element}
}
Document
DOI: 10.4230/DagSemProc.05361.2
A Cost Mechanism for Fair Pricing of Resource Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical; in contrast, a fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (2) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (3) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just $2$ when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. A Cost Mechanism for Fair Pricing of Resource Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.2,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{A Cost Mechanism for Fair Pricing of Resource Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.2},
  URN =		{urn:nbn:de:0030-drops-5646},
  doi =		{10.4230/DagSemProc.05361.2},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}
Document
DOI: 10.4230/DagSemProc.05361.5
Cost Sharing Mechanisms for Fair Pricing of Resources Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical. In contrast, we have been able to prove that pure Nash equilibria do exist for two closely related cost sharing models, namely the Average Cost Pricing and the Serial Cost Sharing models. (2) A fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (3) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (4) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just 2 when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. Cost Sharing Mechanisms for Fair Pricing of Resources Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.5,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{Cost Sharing Mechanisms for Fair Pricing of Resources Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.5},
  URN =		{urn:nbn:de:0030-drops-5665},
  doi =		{10.4230/DagSemProc.05361.5},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}

Spirakis, Paul

Document
Complete Volume
DOI: 10.4230/LIPIcs.SAND.2023
LIPIcs, Volume 257, SAND 2023, Complete Volume

Authors: David Doty and Paul Spirakis

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
LIPIcs, Volume 257, SAND 2023, Complete Volume
Cite as

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1-278, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{doty_et_al:LIPIcs.SAND.2023,
  title =	{{LIPIcs, Volume 257, SAND 2023, Complete Volume}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1--278},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023},
  URN =		{urn:nbn:de:0030-drops-179357},
  doi =		{10.4230/LIPIcs.SAND.2023},
  annote =	{Keywords: LIPIcs, Volume 257, SAND 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SAND.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: David Doty and Paul Spirakis

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.SAND.2023.0,
  author =	{Doty, David and Spirakis, Paul},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.0},
  URN =		{urn:nbn:de:0030-drops-179367},
  doi =		{10.4230/LIPIcs.SAND.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.44
Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols

Authors: Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper we consider a known variant of the standard population protocol model in which agents can be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time. The main focus in this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. - We propose and analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n). - The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart. - We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0.
Cite as

Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak. Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.DISC.2022.44,
  author =	{G\k{a}sieniec, Leszek and Spirakis, Paul and Stachowiak, Grzegorz},
  title =	{{Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{44:1--44:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.44},
  URN =		{urn:nbn:de:0030-drops-172351},
  doi =		{10.4230/LIPIcs.DISC.2022.44},
  annote =	{Keywords: Population protocols, network constructors, probabilistic bubble-sort, self-replication}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.28
MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems

Authors: Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Let V be a set of n vertices, M a set of m labels, and let 𝐑 be an m × n matrix of independent Bernoulli random variables with probability of success p; columns of 𝐑 are incidence vectors of label sets assigned to vertices. A random instance G(V, E, 𝐑^T 𝐑) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely [𝐑^T 𝐑]_{v,u}) between any two vertices u, v for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given G(V, E, 𝐑^T 𝐑) we wish to find a partition of V into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized. In particular, we initially prove that the weight of a maximum cut of G(V, E, 𝐑^T 𝐑) is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, m = n^α, α < 1), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case n = m and constant average degree (i.e. p = Θ(1)/n), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in G(V, E, 𝐑^T 𝐑) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system Σ with incidence matrix 𝐑 (i.e. minimum imbalance over all sets in Σ). We exploit this connection by proposing a (weak) bipartization algorithm for the case m = n, p = Θ(1)/n that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix 𝐑. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in G(V, E, 𝐑^T 𝐑). Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when p = c/n, c < 1.
Cite as

Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nikoletseas_et_al:LIPIcs.ISAAC.2021.28,
  author =	{Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul},
  title =	{{MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.28},
  URN =		{urn:nbn:de:0030-drops-154612},
  doi =		{10.4230/LIPIcs.ISAAC.2021.28},
  annote =	{Keywords: Random Intersection Graphs, Maximum Cut, Discrepancy}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2018
LIPIcs, Volume 117, MFCS'18, Complete Volume

Authors: Igor Potapov, Paul Spirakis, and James Worrell

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
LIPIcs, Volume 117, MFCS'18, Complete Volume
Cite as

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{potapov_et_al:LIPIcs.MFCS.2018,
  title =	{{LIPIcs, Volume 117, MFCS'18, Complete Volume}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018},
  URN =		{urn:nbn:de:0030-drops-97459},
  doi =		{10.4230/LIPIcs.MFCS.2018},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Igor Potapov, Paul Spirakis, and James Worrell

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{potapov_et_al:LIPIcs.MFCS.2018.0,
  author =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.0},
  URN =		{urn:nbn:de:0030-drops-95824},
  doi =		{10.4230/LIPIcs.MFCS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.30
Strategic Contention Resolution with Limited Feedback

Authors: George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.
Cite as

George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. Strategic Contention Resolution with Limited Feedback. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ESA.2016.30,
  author =	{Christodoulou, George and Gairing, Martin and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul},
  title =	{{Strategic Contention Resolution with Limited Feedback}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.30},
  URN =		{urn:nbn:de:0030-drops-63813},
  doi =		{10.4230/LIPIcs.ESA.2016.30},
  annote =	{Keywords: contention resolution, acknowledgment-based protocols, game theory}
}
Document
DOI: 10.4230/DagSemProc.09371.4
On the Fairness of Probabilistic Schedulers for Population Protocols

Authors: Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. cite{AADFP04}, are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.
Cite as

Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis. On the Fairness of Probabilistic Schedulers for Population Protocols. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chatzigiannakis_et_al:DagSemProc.09371.4,
  author =	{Chatzigiannakis, Ioannis and Dolev, Shlomi and Fekete, S\'{a}ndor and Michail, Othon and Spirakis, Paul},
  title =	{{On the Fairness of Probabilistic Schedulers for Population Protocols}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.4},
  URN =		{urn:nbn:de:0030-drops-24286},
  doi =		{10.4230/DagSemProc.09371.4},
  annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact