37 Search Results for "Spirakis, Paul G."

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.SAND.2023.1
Snapshot Disjointness in Temporal Graphs

Authors: Allen Ibiapina and Ana Silva

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

Abstract
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NP-complete, where one multiedge uv is the set of all edges with endpoints u and v.
Cite as

Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1,
  author =	{Ibiapina, Allen and Silva, Ana},
  title =	{{Snapshot Disjointness in Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1:1--1:20},
  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.1},
  URN =		{urn:nbn:de:0030-drops-179379},
  doi =		{10.4230/LIPIcs.SAND.2023.1},
  annote =	{Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.2
Partial Gathering of Mobile Agents in Dynamic Tori

Authors: Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim

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

Abstract
In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic tori. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g (< k), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. So far, in almost cases, the partial gathering problem has been considered in static graphs. As only one exception, it is considered in a kind of dynamic rings called 1-interval connected rings, that is, one of the links in the ring may be missing at each time step. In this paper, we consider partial gathering in another dynamic topology. Concretely, we consider it in n× n dynamic tori such that each of row rings and column rings is represented as a 1-interval connected ring. In such networks, when k = O(gn), focusing on the relationship between the values of k, n, and g, we aim to characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that agents cannot solve the problem when k = o(gn), which means that Ω (gn) agents are necessary to solve the problem. Second, we show that the problem can be solved with the total number of O(gn³) moves when 2gn+2n-1 ≤ k ≤ 2gn + 6n +16g -12. Finally, we show that the problem can be solved with the total number of O(gn²) moves when k ≥ 2gn + 6n +16g -11. From these results, we show that our algorithms can solve the partial gathering problem in dynamic tori with the asymptotically optimal number Θ (gn) of agents. In addition, we show that agents require a total number of Ω(gn²) moves to solve the partial gathering problem in dynamic tori when k = Θ(gn). Thus, when k ≥ 2gn+6n+16g -11, our algorithm can solve the problem with asymptotically optimal number O(gn²) of agent moves.
Cite as

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial Gathering of Mobile Agents in Dynamic Tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 2:1-2:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.SAND.2023.2,
  author =	{Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan},
  title =	{{Partial Gathering of Mobile Agents in Dynamic Tori}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{2:1--2:22},
  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.2},
  URN =		{urn:nbn:de:0030-drops-179387},
  doi =		{10.4230/LIPIcs.SAND.2023.2},
  annote =	{Keywords: distributed system, mobile agents, partial gathering, dynamic tori}
}
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
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.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.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
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
DOI: 10.4230/LIPIcs.STACS.2020.17
On the Termination of Flooding

Authors: Walter Hussak and Amitabh Trehan

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Flooding is among the simplest and most fundamental of all graph/network algorithms. Consider a (distributed network in the form of a) finite undirected graph G with a distinguished node v that begins flooding by sending copies of the same message to all its neighbours and the neighbours, in the next round, forward the message to all and only the neighbours they did not receive the message from in that round and so on. We assume that nodes do not keep a record of the flooding event, thus, raising the possibility that messages may circulate infinitely even on a finite graph. We call this history-less process amnesiac flooding (to distinguish from a classic distributed implementation of flooding that maintains a history of received messages to ensure a node never sends the same message again). Flooding will terminate when no node in G sends a message in a round, and, thus, subsequent rounds. As far as we know, the question of termination for amnesiac flooding has not been settled - rather, non-termination is implicitly assumed. In this paper, we show that surprisingly synchronous amnesiac flooding always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. In particular, synchronous flooding terminates in e rounds, where e is the eccentricity of the source node, if and only if G is bipartite, and, otherwise, in j rounds where e < j ≤ e+d+1 and d is the diameter of G. Since e is bounded above by d, this implies termination times of at most d and of at most 2d + 1 for bipartite and non-bipartite graphs respectively. This suggests that if communication/broadcast to all nodes is the motivation, the history-less amnesiac flooding is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. Moreover, the clear separation in the termination times of bipartite and non-bipartite graphs may suggest possible mechanisms for distributed discovery of the topology/distances in an arbitrary graph. For comparison, we also show that, for asynchronous networks, however, an adversary can force the process to be non-terminating.
Cite as

Walter Hussak and Amitabh Trehan. On the Termination of Flooding. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 17:1-17:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hussak_et_al:LIPIcs.STACS.2020.17,
  author =	{Hussak, Walter and Trehan, Amitabh},
  title =	{{On the Termination of Flooding}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.17},
  URN =		{urn:nbn:de:0030-drops-118786},
  doi =		{10.4230/LIPIcs.STACS.2020.17},
  annote =	{Keywords: Flooding algorithm, Network algorithms, Distributed algorithms, Graph theory, Termination, Bipartiteness, Communication, Broadcast}
}
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}
}
  • Refine by Author
  • 18 Spirakis, Paul G.
  • 8 Mertzios, George B.
  • 4 Deligkas, Argyrios
  • 4 Zamaraev, Viktor
  • 3 Stachowiak, Grzegorz
  • Show More...

  • Refine by Classification
  • 10 Mathematics of computing → Graph algorithms
  • 7 Mathematics of computing → Graph theory
  • 7 Theory of computation → Graph algorithms analysis
  • 4 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 3 Temporal graph
  • 2 Algorithms
  • 2 Cost Sharing
  • 2 Diffuse Price of Anarchy
  • 2 Fair Pricing
  • Show More...

  • Refine by Type
  • 37 document

  • Refine by Publication Year
  • 17 2018
  • 4 2023
  • 3 2017
  • 3 2020
  • 3 2022
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact