33 Search Results for "Pelc, Andrzej"

Document
DOI: 10.4230/LIPIcs.STACS.2026.18
Optimal Deterministic Rendezvous in Labeled Lines

Authors: Yann Bourreau, Ananth Narayanan, and Alexandre Nolin

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds and measured from the moment an agent first wakes up. We denote by τ the delay between the two agents' wake up times. If awake in a given round T, an agent at a node v has three options: stay at the node v, take port 0, or take port 1. If it decides to stay, the agent will still be at node v in round T+1. Otherwise, it will be at one of the two neighbors of v on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem. The problem was recently considered by Miller and Pelc [Distributed Computing, 2025]. With 𝓁_{max} the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in o(D log^* 𝓁_{max}) rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up (τ = 0) and are told their initial distance D. Miller and Pelc also gave an algorithm of optimal matching complexity O(D log^* 𝓁_{max}) when the agents know D, but only obtained the higher bound of O(D² (log^* 𝓁_{max})³) when D is unknown to the agents. In this paper, we improve this second complexity to a tight O(D log^* 𝓁_{max}), closing the gap between the best known lower and upper bounds. In fact, our algorithm achieves rendezvous in O(D log^* 𝓁_{min}) rounds, where 𝓁_{min} is the smallest label within distance O(D) of the two starting positions. We obtain this result by having the agents compute sparse subsets of the nodes to gather at (formally, ruling sets over the line), as well as some general observations about the setting of rendezvous on labeled graphs.
Cite as

Yann Bourreau, Ananth Narayanan, and Alexandre Nolin. Optimal Deterministic Rendezvous in Labeled Lines. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bourreau_et_al:LIPIcs.STACS.2026.18,
  author =	{Bourreau, Yann and Narayanan, Ananth and Nolin, Alexandre},
  title =	{{Optimal Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.18},
  URN =		{urn:nbn:de:0030-drops-255071},
  doi =		{10.4230/LIPIcs.STACS.2026.18},
  annote =	{Keywords: mobile agents, rendezvous, ruling set, deterministic algorithms, labeled line}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.36
Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

Authors: Yi-Jun Chang, Lyuting Chen, and Haoran Zhou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. They showed that in 2-edge-connected networks, any distributed algorithm can be simulated in the content-oblivious model, provided that a unique leader is designated a priori. Subsequent works of Frei, Gelles, Ghazy, and Nolin (DISC 2024) and Chalopin et al. (DISC 2025) developed content-oblivious leader election algorithms, first for unoriented rings and then for general 2-edge-connected graphs. These results establish that all graph problems are solvable in content-oblivious, 2-edge-connected networks. Much less is known about networks that are not 2-edge-connected. Censor-Hillel, Cohen, Gelles, and Sela showed that no non-constant function f(x,y) can be computed correctly by two parties using content-oblivious communication over a single edge, where one party holds x and the other holds y. This seemingly ruled out many natural graph problems on non-2-edge-connected graphs. In this work, we show that, with the knowledge of network topology G, leader election is possible in a wide range of graphs. Our main contributions are as follows: Impossibility: Graphs symmetric about an edge admit no randomized terminating leader election algorithm, even when nodes have unique identifiers and full knowledge of G. Leader election algorithms: Trees that are not symmetric about any edge admit a quiescently terminating leader election algorithm with topology knowledge, even in anonymous networks, using O(n²) messages, where n is the number of nodes. Moreover, even-diameter trees admit a terminating leader election given only the knowledge of the network diameter D = 2r, with message complexity O(nr). Necessity of topology knowledge: In the family of graphs 𝒢 = {P₃, P₅}, both the 3-path P₃ and the 5-path P₅ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to 𝒢, then terminating leader election is impossible.
Cite as

Yi-Jun Chang, Lyuting Chen, and Haoran Zhou. Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.ITCS.2026.36,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Zhou, Haoran},
  title =	{{Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{36:1--36:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.36},
  URN =		{urn:nbn:de:0030-drops-253239},
  doi =		{10.4230/LIPIcs.ITCS.2026.36},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.14
Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Authors: Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc. Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.OPODIS.2025.14,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej},
  title =	{{Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.14},
  URN =		{urn:nbn:de:0030-drops-251874},
  doi =		{10.4230/LIPIcs.OPODIS.2025.14},
  annote =	{Keywords: radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.34
Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice

Authors: Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Radio Networks (RN) is one of the fundamental models for network communication where nodes can broadcast messages locally but their simultaneous transmissions can interfere with each other at their shared neighbors. This work focuses on performing the very fundamental primitive of Local Broadcast, in spite of the interferences. We investigate to what extent local knowledge, called advice, relating to the 2-local domination number γ₂ may speed up Local Broadcast. Specifically for each node and some dominating set, knowledge about some neighboring dominating node and the local number among the neighbors of that dominating node. We show that such advice is sufficient to build an efficient oblivious transmission schedule. Along those lines, we present three algorithms trading the level of adaptiveness (from oblivious to adaptive) for bits of advice per node (from O(log (Δγ₂)) to 1). All our algorithms complete Local Broadcast in Õ(Δγ₂²) rounds, where Δ is the maximum degree of the network. On the side of lower bounds, we show that, for each quasi-adaptive deterministic Local Broadcast algorithm, there is some RN that requires Ω(min{(min{Δ,γ₂}/log n)²,n}) communication rounds, where n is the number of network nodes. In quasi-adaptive protocols nodes may stop executing once its computational task is completed. To the best of our knowledge, this is the first (nearly) quadratic Local Broadcast (same message for all neighbors) lower bound in the RN model. Our lower bound is stronger than previous works in multiple ways: i) it is nearly quadratically better than the best known general lower bound for this class of algorithms, ii) it applies to a wider class of algorithms than previous work for fully oblivious, iii) it achieves similar time lower bound than previous work proved for a much more demanding Local Broadcast where each node sends a possibly different message to each neighbor, and iv) it takes into account the local domination parameter γ₂.
Cite as

Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro. Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garncarek_et_al:LIPIcs.ISAAC.2025.34,
  author =	{Garncarek, Pawel and Jurdzinski, Tomasz and Kowalski, Dariusz R. and Kutten, Shay and Mosteiro, Miguel A.},
  title =	{{Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.34},
  URN =		{urn:nbn:de:0030-drops-249426},
  doi =		{10.4230/LIPIcs.ISAAC.2025.34},
  annote =	{Keywords: Radio Networks, Local Broadcast, Distributed Deterministic Algorithms, Lower Bounds, Graph algorithms, Advice, Labeling Schemes, Local Domination}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.30
Team Formation and Applications

Authors: Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size σ, where σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.
Cite as

Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld. Team Formation and Applications. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2025.30,
  author =	{Emek, Yuval and Kutten, Shay and Rafael, Ido and Taubenfeld, Gadi},
  title =	{{Team Formation and Applications}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.30},
  URN =		{urn:nbn:de:0030-drops-248474},
  doi =		{10.4230/LIPIcs.DISC.2025.30},
  annote =	{Keywords: asynchronous message-passing, complete communication graph, initial failures, leader election, matching}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.34
New Distributed Interactive Proofs for Planarity: A Matter of Left and Right

Authors: Yuval Gil and Merav Parter

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof size. Prior work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O(log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O(log n). In a subsequent work, Bousquet, Feuilloley, and Pierron (OPODIS 2021) achieved the same bound for related graph families such as outerplanarity, series-parallel graphs, and graphs of treewidth at most 2. In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are: - There is a 5-round protocol with O(log log n) proof size for outerplanarity. - There is a 5-round protocol with O(log log n) proof size for verifying embedded planarity and O(log log n+log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω(log n) bits for graphs with Δ = O(1) by Feuilloley et al. (PODC 2020). - The non-interactive deterministic lower bound of Ω(log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier’s randomness comes in the form of an unbounded random string shared among the nodes. We also show that our DIPs can be extended to protocols with similar bounds for verifying series-parallel graphs and graphs with tree-width at most 2. Perhaps surprisingly, our results demonstrate that the key technical barrier for obtaining o(log log n) labels for all our problems is a basic sorting verification task in which all nodes are embedded on an oriented path P ⊆ G and it is desired for each node to distinguish between its left and right G-neighbors.
Cite as

Yuval Gil and Merav Parter. New Distributed Interactive Proofs for Planarity: A Matter of Left and Right. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gil_et_al:LIPIcs.DISC.2025.34,
  author =	{Gil, Yuval and Parter, Merav},
  title =	{{New Distributed Interactive Proofs for Planarity: A Matter of Left and Right}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.34},
  URN =		{urn:nbn:de:0030-drops-248515},
  doi =		{10.4230/LIPIcs.DISC.2025.34},
  annote =	{Keywords: Distributed interactive proofs, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.21
Content-Oblivious Leader Election in 2-Edge-Connected Networks

Authors: Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may arbitrarily corrupt messages. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity O(n ⋅ ID_{max}), where n is the number of nodes and ID_{max} is the maximum ID. The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity O(m ⋅ N ⋅ ID_{min}), where m is the number of edges, N is a known upper bound on the number of nodes, and ID_{min} is the smallest ID. Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity O(n ⋅ ID_{max}) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.
Cite as

Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou. Content-Oblivious Leader Election in 2-Edge-Connected Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2025.21,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chang, Yi-Jun and Chen, Lyuting and Di Luna, Giuseppe A. and Zhou, Haoran},
  title =	{{Content-Oblivious Leader Election in 2-Edge-Connected Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.21},
  URN =		{urn:nbn:de:0030-drops-248385},
  doi =		{10.4230/LIPIcs.DISC.2025.21},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.58
Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Authors: Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc. Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.58,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej},
  title =	{{Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.58},
  URN =		{urn:nbn:de:0030-drops-248744},
  doi =		{10.4230/LIPIcs.DISC.2025.58},
  annote =	{Keywords: radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.12
Distributed Computation with Local Advice

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed Computation with Local Advice. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.12,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Nowicki, Krzysztof and Olivetti, Dennis and Rotenberg, Eva and Suomela, Jukka},
  title =	{{Distributed Computation with Local Advice}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.12},
  URN =		{urn:nbn:de:0030-drops-248295},
  doi =		{10.4230/LIPIcs.DISC.2025.12},
  annote =	{Keywords: Distributed graph algorithms, LOCAL model, computation with advice, locally checkable labeling problems, proof labeling schemes, locally checkable proofs, graph coloring, exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.16
Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Authors: Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.
Cite as

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal. Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.DISC.2025.16,
  author =	{Bhattacharya, Adri and Goswami, Pritam and Bampas, Evangelos and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.16},
  URN =		{urn:nbn:de:0030-drops-248333},
  doi =		{10.4230/LIPIcs.DISC.2025.16},
  annote =	{Keywords: mobile agents, perpetual exploration, malicious host, Byzantine black hole}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.20
Beeping Deterministic CONGEST Algorithms in Graphs

Authors: Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Beeping Network (BN) is a popular graph-based model of wireless computation, which applies the OR operation to one-bit messages sent simultaneously by neighbors. It admits fast (polylogarithmic in the number of nodes n) randomized solutions to many graph problems, but all known deterministic algorithms for non-trivial graph problems are at least polynomial in the maximum node degree Δ. We improve known results for deterministic algorithms by showing that this polynomial can be as low as Õ(Δ²). More precisely, we show how to simulate a single round of any CONGEST algorithm in any network in O(Δ² polylog n) beeping rounds, each accommodating at most one beep per node, even if the nodes intend to send different messages to different neighbors. This upper bound reduces polynomially the time for a deterministic simulation of CONGEST in a Beeping Network, comparing to the best known algorithms, and nearly matches the time obtained recently using randomization (up to a poly-logarithmic factor) as well as the lower bound. Specifically, any algorithm designed for the CONGEST networks can be run in BNs with O(Δ² polylog n) multiplicative overhead, e.g., we can now deterministically compute an MIS in any BN in O(Δ² polylog n) beeping rounds, improving the previous best Θ(Δ³)-round solution. For h-hop simulations, we prove a lower bound Ω(Δ^{h+1}), and we design a nearly matching algorithm that is able to "pipeline" the node-to-node information in a faster way than beeping layer-by-layer.
Cite as

Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro. Beeping Deterministic CONGEST Algorithms in Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garncarek_et_al:LIPIcs.ESA.2025.20,
  author =	{Garncarek, Pawel and Kowalski, Dariusz R. and Kutten, Shay and Mosteiro, Miguel A.},
  title =	{{Beeping Deterministic CONGEST Algorithms in Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.20},
  URN =		{urn:nbn:de:0030-drops-244880},
  doi =		{10.4230/LIPIcs.ESA.2025.20},
  annote =	{Keywords: Beeping Networks, CONGEST Networks, deterministic simulations, graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.24
Computational Geometry with Probabilistically Noisy Primitive Operations

Authors: David Eppstein, Michael T. Goodrich, and Vinesh Sridhar

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.
Cite as

David Eppstein, Michael T. Goodrich, and Vinesh Sridhar. Computational Geometry with Probabilistically Noisy Primitive Operations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.WADS.2025.24,
  author =	{Eppstein, David and Goodrich, Michael T. and Sridhar, Vinesh},
  title =	{{Computational Geometry with Probabilistically Noisy Primitive Operations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24},
  URN =		{urn:nbn:de:0030-drops-242552},
  doi =		{10.4230/LIPIcs.WADS.2025.24},
  annote =	{Keywords: Computational geometry, noisy comparisons, random walks}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.42
Broadcasting Under Structural Restrictions

Authors: Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In the Telephone Broadcast problem we are given a graph G = (V,E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).
Cite as

Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Broadcasting Under Structural Restrictions. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{egami_et_al:LIPIcs.MFCS.2025.42,
  author =	{Egami, Yudai and Gima, Tatsuya and Hanaka, Tesshu and Kobayashi, Yasuaki and Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Broadcasting Under Structural Restrictions}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.42},
  URN =		{urn:nbn:de:0030-drops-241492},
  doi =		{10.4230/LIPIcs.MFCS.2025.42},
  annote =	{Keywords: Parameterized Complexity, Structural Graph Parameters, Telephone Broadcast}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2025.7
Temporal Explorability Games

Authors: Pete Austin, Sougata Bose, Nicolas Mazzocchi, and Patrick Totzke

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
Temporal graphs extend ordinary graphs with discrete time that affects the availability of edges. We consider solving games played on temporal graphs where one player aims to explore the graph, i.e., visit all vertices. The complexity depends majorly on two factors: the presence of an adversary and how edge availability is specified. We demonstrate that on static graphs, where edges are always available, solving explorability games is just as hard as solving reachability games. In contrast, on temporal graphs, the complexity of explorability coincides with generalized reachability (NP-complete for one-player and PSPACE-complete for two player games). We show that if temporal graphs are given symbolically, even one-player reachability (and thus explorability and generalized reachability) games are PSPACE-hard. For one player, all these are also solvable in PSPACE and for two players, they are in PSPACE, EXP and EXP, respectively.
Cite as

Pete Austin, Sougata Bose, Nicolas Mazzocchi, and Patrick Totzke. Temporal Explorability Games. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austin_et_al:LIPIcs.CONCUR.2025.7,
  author =	{Austin, Pete and Bose, Sougata and Mazzocchi, Nicolas and Totzke, Patrick},
  title =	{{Temporal Explorability Games}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.7},
  URN =		{urn:nbn:de:0030-drops-239575},
  doi =		{10.4230/LIPIcs.CONCUR.2025.7},
  annote =	{Keywords: Temporal Graphs, Explorability, Reachability, Games}
}
  • Refine by Type
  • 33 Document/PDF
  • 26 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 23 2025
  • 1 2023
  • 1 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 11 Pelc, Andrzej
  • 4 Jurdzinski, Tomasz
  • 3 Dieudonné, Yoann
  • 3 Ganczorz, Adam
  • 3 Kutten, Shay
  • Show More...

  • Refine by Series/Journal
  • 33 LIPIcs

  • Refine by Classification
  • 23 Theory of computation → Distributed algorithms
  • 7 Theory of computation → Design and analysis of algorithms
  • 2 Computing methodologies → Mobile agents
  • 2 Mathematics of computing → Graph algorithms
  • 1 Computer systems organization → Fault-tolerant network topologies
  • Show More...

  • Refine by Keyword
  • 9 mobile agent
  • 4 graph
  • 4 rendezvous
  • 3 exploration
  • 3 labeling scheme
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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