Open questions

Graph exploration by a single agent

Arbitrary graphs, perpetual exploration static graph · undirected · perpetual

1. What is the time of memory-optimal perpetual exploration, and is there a trade-off between memory and time?

Trees, exploration with stop static graph · undirected · with stop · tree

1. Can exploration with stop on trees use asymptotically less memory than exploration with return? (Open problem of Diks et al. 2004.) Equivalently: close \(\Omega(\log\log\log n)\) versus \(O(\log n)\).

Exploration with return and pebbles static graph · undirected · pebbles

1. How much memory is needed to encode the agent's transition function? The naive table needs \((\log n)^{O(1)}\) bits (Remark 1 of Disser et al. 2019).

Exploration with stop when \(n\) is known static graph · undirected · knows a bound on \(n\) · with stop

1. Is \(\Omega(\log n)\) bits necessary when \(n\) is known? The trap arguments Fraigniaud et al. 2005a are stated for agents that know nothing.

Randomized exploration when \(n\) is known static graph · undirected · knows a bound on \(n\) · private coins · with stop

1. What is the memory needed by a randomized agent that must stop correctly with high probability, as a function of \(n\)?

Exploration with stop and one pebble static graph · undirected · one pebble · with stop

1. Is \(\Omega(D\log\Delta)\) memory needed for exploration with stop by an agent with one pebble Fraigniaud et al. 2005b?

Port numbers chosen by the designer (periodic exploration) static graph · undirected · designer ports · perpetual

1. Close the constant gaps: \(2n-2\) versus \(3.5n-2\) for constant memory, \(2.8n - O(1)\) versus \(4n-2\) for oblivious agents Czyzowicz et al. 2012c Kosowski & Navarra 2012.

2. Trade-offs between period and memory: the only lower bound for agents with memory does not depend on memory.

Directed graphs, one pebble static graph · one pebble · with stop

1. Close \(\Omega(n\log\Delta_{out})\) versus \(O(n\Delta_{out}\log n)\) bits for exploring digraphs with one pebble.

2. Determine the trade-off between time and memory: polynomial-time exploration with stop is known only with \(O(n^2\Delta_{out}\log n)\) bits and \(O(\log\log n)\) pebbles, far from the \(\Omega(n\log\Delta_{out})\) lower bound (Section 5 of Fraigniaud & Ilcinkas 2004).

Directed graphs, one pebble, bound on \(n\) known static graph · knows a bound on \(n\) · one pebble · with stop

1. Improve the \(O(N^2 n^6 \Delta_{out}^2)\) running time (Section 5 of Bender et al. 2002).

Directed graphs with labelled nodes static graph · labelled nodes · with stop

1. Close \(\Omega(\phi^2m)\) versus \(O(\phi^8m)\) for online exploration of digraphs with deficiency \(\phi\).

Temporal graphs, schedule known connected every round · undirected · knows the map · perpetual

1. Tight bounds when the underlying graph is a grid, has bounded degree or is planar Erlebach et al. 2021. For bounded degree and for planar underlying graphs the best bounds known are \(\Omega(n\log n)\) and \(O(n^{3/2}\sqrt{\log n})\) Bastide et al. 2025; the upper bound holds for grids too.

2. For underlying maximum degree \(\Delta\), close the gap between \(\Omega(\Delta n(1+\log(n/\Delta)))\) Carnevale 2026 and \(O(\min\{n^2, n^{3/2}\sqrt{\Delta\log n}\})\) Bastide et al. 2025; for constant \(\Delta\) the bounds are \(\Omega(n\log n)\) and \(O(n^{3/2}\sqrt{\log n})\). The upper bound needs only that every snapshot has maximum degree at most \(\Delta\).

3. When at most \(\mu\) edges are missing in each snapshot, remove the factor \(\mu\) between \(O(\mu n\log\mu)\) Lahtin & Zamaraev 2027 and \(\Omega(n\log\mu)\) (as reported by Lahtin & Zamaraev 2027).

\(T\)-interval-connected graphs, labelled nodes connected every round · undirected · labelled nodes · with stop

1. Close the gap on the window, \(\Omega(m)\) against \(O(\zeta m + n\log^2 n)\); it is at most a \(\log^2 n\) factor and remains when \(m = n^{1+o(1)}\) Sudo et al. 2026c.

2. How much smaller can the window be, and how much faster the exploration, for a randomized agent Sudo et al. 2026c?

3. Close the polylogarithmic gap on the time with 1-hop view, \(\Omega(m)\) against \(O(\zeta m + n\log^2 n)\), and determine exactly what the 1-hop view buys Sudo et al. 2026c.

Collaborative exploration

Connected team, labelled graphs, shared knowledge static graph · undirected · labelled nodes · global communication · synchronous

1. Is there an algorithm with sublinear overhead for \(n > k\) agents? The paper gives experiments only and calls a bound an important milestone Mutzari et al. 2026.

Arbitrary graphs, complete communication static graph · undirected · labelled nodes · global communication · synchronous · free team

1. Is there an \(o(k)\)-competitive collaborative exploration algorithm for arbitrary graphs? (Stated as open in Cosson & Massoulié 2026.)

Trees, complete communication static graph · undirected · labelled nodes · global communication · synchronous · free team · tree

1. Determine the competitive ratio of synchronous collective tree exploration: between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).

2. Do randomized algorithms help? A randomized lower bound of \(\Omega(\sqrt{\log k}/\log\log k)\) is attributed to Ortolf and Schindelhauer (SPAA 2012), not checked here. Cosson and Massoulié conjecture they do not Cosson & Massoulié 2025.

Trees with \(k = n\) agents static graph · undirected · labelled nodes · global communication · synchronous · \(k = n\) · free team · tree

1. For \(k=n\) and trees of depth \(D\) well above \(\sqrt{\log n}\) (e.g. \(D=\sqrt n\)), is \(\Omega(D^2)\) still necessary?

Large teams, complete communication static graph · undirected · labelled nodes · global communication · synchronous · \(k \ge Dn^{1+\varepsilon}\) · free team

1. Which team size is necessary and sufficient for \(O(D)\)-round exploration of graphs of larger diameter? (Stated in Dereniowski et al. 2015a.)

Trees, communication by whiteboards only static graph · undirected · labelled nodes · whiteboards · synchronous · free team · tree

1. Is there a separation between write-read and complete communication? Cosson & Massoulié 2025 conjecture that centralised communication helps.

Trees, asynchronous, whiteboards only static graph · undirected · labelled nodes · whiteboards · free team · tree

1. Is there a distributed asynchronous algorithm with polylogarithmic competitive ratio?

Anonymous graphs with \(k = n\) agents static graph · undirected · local communication · synchronous · \(k = n\) · free team

1. Can \(n\) agents explore an anonymous tree in \(o(n)\) rounds, e.g. \(O(D^2)\), with local communication? With labelled nodes and global communication \(D^2\) suffices Disser et al. 2020.

Dispersion

Asynchronous agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication

1. Can an asynchronous algorithm let every agent terminate in polynomial time without knowledge of the graph? The only terminating asynchronous algorithm known uses \(O(\Delta^{\min(D,k)+1})\) time Kshemkalyani 2025; the linear-time algorithms keep settled agents active.

2. Semi-synchronous schedulers sit between the two models; no separation or dedicated bound is known.

Arbitrary graph, arbitrary initial configuration static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Can the memory be reduced to \(O(\log k)\) bits, independent of \(\Delta\), while keeping \(O(k)\) time? Equivalently, is there an \(\Omega(\log\Delta)\) memory lower bound for deterministic agents with identifiers? The bound \(\Omega(\log(k+\Delta))\) is quoted in several papers but only the \(\log k\) term is argued.

2. Can all agents terminate explicitly in \(O(k)\) rounds without any knowledge of \(k\), \(m\) or \(\Delta\)? Sudo et al. 2026a terminates the rooted case in \(O(k)\) extra rounds but needs global upper bounds in the general case; Kshemkalyani et al. 2025b does not address termination detection for arbitrary initial configurations.

3. Ongoing dispersion Kshemkalyani & Ali 2019: agents that have settled must periodically leave (for example to recharge) and the configuration must be re-dispersed; no bounds beyond the original proposal are known.

Rooted initial configuration static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · rooted start

1. Is \(O(k)\) time achievable with \(O(\log k)\) bits? Memory \(O(\log(k+\Delta))\) is needed by every known algorithm to remember a port number.

Global communication static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · global communication · synchronous

1. Does global communication buy anything for dispersion? Since \(O(k)\) time with \(O(\log(k+\Delta))\) bits holds with local communication, a separation could only come from memory (\(O(\log k)\) bits), from termination detection, or from the BFS-style question of achieving time close to \(O(D)\)-dependent bounds for small \(D\).

2. Kshemkalyani et al. 2022 asks for \(O(\min(m,k\Delta))\) time with only \(O(\log(k+\Delta))\) bits in the global model; this is implied by the later local-model result, so the live version of the question is the memory question above.

Silent agents (no communication) static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · synchronous

1. Close the time gap on general graphs: is \(O(k + \log L)\) achievable, as on rings?

2. Arbitrary (multi-source) initial configurations on general graphs; only rings are solved Das et al. 2026a.

3. Weaker sensing: agents that only learn whether they are alone and whether the count decreased, and agents that wake up at different times (a 2026 ICDCIT paper by Gorain, Mandal and Sharma treats this; its bounds are not recorded here).

Oriented grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · grid · oriented · no faults · local communication · synchronous

1. Rectangular \(W \times H\) oriented grids with \(W \le H\): from a corner at most \(W(t+1)\) nodes are reachable in \(t\) rounds, so \(\lceil k/W\rceil - 1\) rounds are needed; an algorithm matching a bound that depends on \(W\) and \(H\), with local communication and no knowledge of \(W\) and \(H\), is open Kumar et al. 2026a.

2. \(O(\sqrt k)\) rounds on oriented grids with asynchronous agents, or on the oriented torus Kumar et al. 2026a.

3. Dispersion in \(O(\sqrt k)\) rounds on oriented grids with explicit termination: every agent knows when it may stop (see notes).

Crash faults on oriented grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · grid · oriented · at most crash faults · local communication · synchronous

1. Crash-tolerant dispersion in \(O(\sqrt k)\) rounds on oriented grids for \(k = o(n)\); the fault-free case is solved by Kumar et al. 2026a (preprint), which names fault tolerance as future work.

Weak Byzantine agents on oriented grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · grid · oriented · at most weak Byzantine faults · local communication · synchronous

1. Reduce the memory below \(O(n\log n)\) bits on grids with weak Byzantine agents.

2. Strong Byzantine agents (able to fake identifiers) on grids Banerjee et al. 2025.

3. Weak Byzantine agents on unoriented grids, and on oriented grids with \(k = o(n)\) agents in \(O(\sqrt k)\) rounds; fault tolerance is named as future work in Kumar et al. 2026a.

Unoriented grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · grid · no faults · local communication · synchronous

1. Can \(k \le n\) agents disperse on an unoriented grid in \(O(\sqrt k)\) rounds with local communication? On oriented grids \(O(\sqrt k)\) rounds are reached with local communication Kumar et al. 2026a (preprint), and with global communication by Kshemkalyani et al. 2020c (as reported); asked in Banerjee et al. 2025, and for unoriented grids in Kumar et al. 2026a.

2. A lower bound in terms of \(k\) for \(k = o(\sqrt n)\) with \(O(\log n)\) memory on unoriented grids Banerjee et al. 2024.

3. Unoriented grids with no knowledge of \(n\) and with faults, matching the fault-free bounds Banerjee et al. 2024.

Crash faults on unoriented grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · grid · at most crash faults · local communication · synchronous

1. Unoriented grids with crashes: close the gap between \(O(\sqrt n\log n)\) rounds with \(O(\sqrt n\log n)\) bits and the fault-free \(O(\sqrt n)\) rounds with \(O(\log n)\) bits Banerjee et al. 2024.

Rings and paths static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · ring · no faults · local communication · synchronous

1. Anonymous randomized agents disperse from a rooted ring configuration with \(O(1)\) bits in \(O(n)\) rounds Molla & Moses Jr. 2019. From an arbitrary configuration the known algorithm never terminates; is \(O(1)\)-bit dispersion with termination possible on rings?

Silent agents on rings static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · ring · no faults · synchronous

1. Unoriented rings, and rings where agents cannot detect count changes.

Weak Byzantine agents on rings static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · ring · at most weak Byzantine faults · local communication · synchronous

1. Keep \(O(n)\) time and \(O(\log n)\) bits while dropping any of: identifiers in \([1,n]\), knowledge of \(f\), the bound \(f \le (n-4)/17\), the follow primitive Molla et al. 2021a.

2. Asynchronous Byzantine dispersion on rings Molla et al. 2021a.

Trees static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · tree · no faults · local communication · synchronous

1. Augustine & Moses Jr. 2018 asked for \(o(n)\)-round dispersion on arbitrary trees. Precisely: for \(k = n\) and an arbitrary initial configuration, is there an algorithm whose time is bounded by a function of \(D\) alone, ideally \(O(D^2)\) as in the rooted case? No tree-specific algorithm has appeared since 2018; the linear-time general algorithms give only \(O(n)\).

2. With global communication, trees admit \(O(D\cdot\max(D,k))\) rounds with \(O(\max(D, \Delta\log k))\) bits (arXiv version of Kshemkalyani et al. 2020b); whether the \(\max(D,k)\) factor can be reduced to \(D\), and whether local communication suffices, is open.

Rooted trees static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · tree · no faults · local communication · synchronous · rooted start

1. For \(k < n\) the lower bound \(\Omega(D^2)\) no longer applies (only \(k\) nodes must be reached). Whether \(O(\min(k, D^2))\) time is achievable, and whether it is necessary, has not been addressed.

2. For \(k=n\) agents rooted on a tree of height \(D\) much larger than \(\sqrt{\log n}\), is \(\Omega(D^2)\) time necessary? The known bound is existential in \(D\) Disser et al. 2020.

Crash faults static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most crash faults · local communication · synchronous

1. Is \(O(k)\) time achievable with crash faults, or does fault tolerance cost a factor of \(\Delta\)? No lower bound beyond the fault-free \(\Omega(k)\) is known, even with \(O(\log(k+\Delta))\) memory Chand et al. 2025a.

2. Simultaneously \(O(\min(m,k\Delta))\) (or better) time and \(O(\log(k+\Delta))\) memory for arbitrary configurations, without knowledge of \(f\), \(\ell\), \(\Delta\) or \(m\) Chand et al. 2025a Pattanayak et al. 2023.

3. Crash faults under asynchrony: no result exists.

Weak Byzantine agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most weak Byzantine faults · local communication · synchronous

1. Faster Byzantine dispersion on general graphs: the time is dominated by Byzantine gathering, and the authors ask whether building a map before settling is necessary Molla et al. 2021b.

2. Tolerating more than \(n/2\) weak Byzantine agents on general graphs (possible only on the restricted class so far) Molla et al. 2021b.

3. Byzantine dispersion with bounded memory per agent, on trees, with \(k < n\), or under asynchrony: nothing is known Molla et al. 2021a Chand et al. 2025a.

Strong Byzantine agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · local communication · synchronous

1. Polynomial-time strong-Byzantine dispersion from arbitrary configurations without a trusted agent, and the largest tolerable \(f\).

2. Asynchronous versions: a slow agent cannot be distinguished from a silent Byzantine one Moses Jr. & Redlich 2024.

Anonymous agents with randomness static graph · undirected · \(k \le n\) · private coins · no faults · local communication · synchronous

1. Close the gap between \(\Omega(k)\) and \(\Theta(k^2)\) rounds for anonymous agents from a rooted configuration with \(O(\log\Delta)\) bits Das et al. 2023.

2. Can anonymous randomized agents disperse from an arbitrary configuration and then stop, rather than staying active forever? Molla & Moses Jr. 2019 Das et al. 2023

3. On rings the memory bound is \(O(1)\); is \(O(1)\)-bit dispersion with termination possible on rings from arbitrary configurations?

More agents than nodes static graph · undirected · private coins · no faults · local communication · synchronous

1. Deterministic dispersion with \(k > n\) agents with identifiers on static graphs has not been studied: no algorithm and no lower bound beyond \(\Omega(k)\) is recorded in the literature surveyed here. (Related work exists only on dynamic rings and dynamic graphs under the name balanced dispersion.)

2. Is \(O(k)\) time possible for rooted configurations when \(k > n\), matching the \(k \le n\) case?

3. Terminating dispersion with \(k > n\) on general rooted graphs with \(O(\log\Delta)\) bits per agent (Open Problem 2 of Molla & Moses Jr. 2019).

Directed graphs static graph · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Close the time gaps; in particular \(O((k+f)k\Delta_{out})\) with \(f\) crashes Italiano et al. 2025.

2. BFS-based dispersion in the local model, without 1-hop communication Italiano et al. 2025.

3. Dispersion on dynamic directed graphs, and in semi-synchronous and asynchronous settings Italiano et al. 2025.

Directed graphs, 1-hop communication static graph · \(k \le n\) · distinct IDs (eponymous) · no faults · \(h\)-hop communication · synchronous

1. A BFS-based algorithm with \(O(\log(k+\Delta_{out}))\) bits per agent, as with local communication Italiano et al. 2025.

2. Does \(O(kD)\) improve to \(O(k + D^2)\) or \(O(k)\) with 1-hop communication?

Dynamic graphs (1-interval connected) connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Which combination of communication range and visibility is necessary for dispersion on \(T\)-interval connected graphs with \(T > 1\), where the impossibility proof for \(T = 1\) does not apply? Saxena & Mondal 2025

2. Dynamic graphs with a bounded number of missing edges per round: Saxena et al. 2026a gives impossibilities on 1-bounded 1-interval connected graphs for several weaker communication and visibility combinations and an \(O(k)\) algorithm with global communication and 1-hop visibility; the local-communication case with few missing edges is not settled.

Dynamic graphs with global communication connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · global communication · synchronous

1. Byzantine agents on dynamic graphs Kshemkalyani et al. 2020a.

2. Memory \(O(\log k)\) instead of \(O(\log\max(k,T))\) on \(T\)-path connected graphs when \(T\) need not be known Saxena & Mondal 2025.

Dynamic rings connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · ring · no faults · local communication · synchronous

1. Visibility strictly between none and full: how much must an agent see of a dynamic ring for dispersion to be possible? Agarwalla et al. 2018

2. Achiral agents on even rings of size at least 6 under vertex permutation and 1-interval connectivity: is \(O(n)\) time possible from arbitrary configurations? Agarwalla et al. 2018; \(O(\ell n)\) is known without vertex permutation Mondal et al. 2025b.

Uniform deployment on graphs

Dynamic rings, all agents but one connected every round · undirected · no faults · synchronous · ring · dispersed start · all but one

1. Is \(O(n)\) time possible on a 1-interval connected ring? Shibata et al. 2022a reach \(O(n\log k)\) against \(\Omega(n)\) and leave the lower bound on time to future work.

2. Can almost uniform deployment be reached without chirality or without strong multiplicity detection Shibata et al. 2022a?

Treasure hunt

Anonymous finite graphs static graph · undirected · finite graph

1. Treasure hunt when the treasure may appear after the agent starts and the agent does not see its entry port: "We do not know if an efficient solution is possible when backtracking is not allowed" Ta-Shma & Zwick 2014.

2. Do strongly universal traversal sequences exist? They exist if and only if treasure hunt has a solution independent of the start time Ta-Shma & Zwick 2014.

3. Is there a strongly universal exploration sequence with cover time \(O(n^{\theta})\), or \(O(n^{\theta}\log n)\), for fixed-degree graphs? Xin 2026 (preprint) reaches \(O(n^{\theta}\log n\,(\log\log n)^{1+\varepsilon})\) and shows that its recurrence cannot keep linear length with periods \(\Theta(2^j j)\) (Corollary 10.2), which is "not a lower bound for arbitrary SUESs".

Labelled nodes, locally finite graphs static graph · undirected · locally finite · labelled nodes

1. Remove the \(O(\log d)\) factor between \(O(e(d)\log d)\) and \(\Omega(e(d))\) Bouchard et al. 2023a.

Dynamic graphs, connected at every step connected every round · undirected · finite graph

1. With flags in VP(\(\xi\)), the lower bound of \(\xi(n-3)\) steps for one deterministic agent is proved for \(\xi\ge 2n\); does \(\Omega(\xi n)\) hold for every \(\xi\ge\lceil (n-1)/2\rceil\), the smallest window for which VP(\(\xi\)) is non-empty? Ayoubi et al. 2026

2. What is the competitive ratio of randomized agents in VP(\(\xi\)) against an adaptive online adversary? Ayoubi et al. 2026

3. Which of these results extend to vertex-permuted graphs other than rings? Ayoubi et al. 2026

Rendezvous

Asynchronous labelled agents static graph · undirected · finite graph · distinct IDs (eponymous)

1. Find an optimal-cost asynchronous rendezvous algorithm in arbitrary graphs (open problem of Pelc 2019).

Labelled agents, arbitrary finite graphs static graph · undirected · finite graph · distinct IDs (eponymous) · synchronous

1. Find an optimal-time synchronous rendezvous algorithm for labelled agents in arbitrary graphs (open problem of Pelc 2019).

Anonymous agents: memory static graph · undirected · finite graph · synchronous

1. Is there a universal algorithm that meets for every feasible start in time polynomial in \(n\) and \(\tau\)? Posed in Pelc & Yadav 2019b.

Labelled agents in infinite trees static graph · undirected · locally finite · distinct IDs (eponymous) · synchronous · tree

1. Close the gap between \(O(\mathrm{ball}(d)\log L)\) and \(\Omega(\mathrm{ball}(d)+d\log L)\) in unoriented regular trees. Posed in Bhagat & Pelc 2024.

2. Find efficient rendezvous algorithms for arbitrary infinite graphs without extra knowledge such as the agents' positions. Posed in Bhagat & Pelc 2024.

Labelled agents in infinite trees, simultaneous start static graph · undirected · locally finite · distinct IDs (eponymous) · synchronous · simultaneous start · tree

1. In oriented trees with simultaneous start, can agents meet in time \(O(d\log L)\) without knowing anything about \(d\) or \(L\)? Posed in Bhagat & Pelc 2024.

Labelled agents, graphs with infinite degrees static graph · undirected · distinct IDs (eponymous) · synchronous

1. Find an optimal rendezvous algorithm, "even for finite graphs" Pattanayak & Pelc 2024b.

Pattern formation

ASYNC, no agreement on coordinates point · unlimited visibility · transparent · no faults

1. Bound the number of epochs needed by an arbitrary pattern formation algorithm in ASYNC; no time analysis is recorded.

Randomized, ASYNC, chirality point · unlimited visibility · transparent · no faults · chirality · randomized

1. A proof that does not rely on the disputed algorithm of Fujinaga et al. 2015, for example by combining the symmetry-breaking phase of Yamauchi & Yamashita 2014 with the algorithm of Cicerone et al. 2019.

Opaque robots with lights, ASYNC, one axis, rigid point · unlimited visibility · no faults · lights (LUMI) · one axis · rigid

1. The minimum number of colours, and formation with chirality only or with no agreement Bose et al. 2021a.

Limited visibility point · transparent · no faults

1. Arbitrary pattern formation by oblivious robots with limited visibility from a general (connected) initial configuration Hahn et al. 2024.

Gathering

Rendezvous, internal light (FSTA), SSYNC, non-rigid point · unlimited visibility · transparent · no faults · SSYNC · internal light (FSTA) · \(n = 2\)

1. Rendezvous with internal lights in non-rigid SSYNC when \(\delta\) is unknown.

Gathering, internal light (FSTA), SSYNC, non-rigid point · unlimited visibility · transparent · no faults · SSYNC · internal light (FSTA) · chirality · \(n \ge 3\)

1. Gathering with internal lights in SSYNC from every start, with more than 2 colours, and in ASYNC Otaka et al. 2026.

Gathering, external light (FCOM), SSYNC, rigid point · unlimited visibility · transparent · no faults · SSYNC · external light (FCOM) · chirality · rigid · \(n \ge 3\)

1. Gathering with external lights in ASYNC Otaka et al. 2026.

Gathering, full lights, SSYNC, no multiplicity detection point · unlimited visibility · transparent · no faults · SSYNC · lights (LUMI) · chirality · \(n \ge 3\)

1. Gathering with lights without chirality Terai et al. 2023.

Self-stabilizing gathering, full lights, SSYNC, strong multiplicity detection point · unlimited visibility · transparent · no faults · SSYNC · lights (LUMI) · rigid · strong multiplicity

1. Does self-stabilizing gathering with 2 colours extend to ASYNC Bonnet et al. 2026a?

2. Is self-stabilizing SSYNC gathering with lights solvable with weak or no multiplicity detection, or with non-rigid moves? The algorithm of Bonnet et al. 2026a uses strong multiplicity detection and rigid moves.

Homonymous robots, SSYNC point · unlimited visibility · transparent · no faults · SSYNC · homonymous

1. What is the minimum number of identifiers for Byzantine-tolerant gathering? Asahiro & Yamashita 2025

Gathering, full lights, ASYNC, no multiplicity detection point · unlimited visibility · transparent · no faults · lights (LUMI) · chirality · \(n \ge 3\)

1. Is 3 the minimum number of colours for ASYNC gathering with lights, and can chirality be dropped Nakai et al. 2021?

2. Self-stabilizing gathering of \(n\) robots with lights Heriban et al. 2018.

Rendezvous, external light (FCOM), ASYNC, non-rigid point · unlimited visibility · transparent · no faults · external light (FCOM) · \(n = 2\)

1. Rendezvous with external lights in non-rigid ASYNC when \(\delta\) is unknown Flocchini et al. 2016a Wada et al. 2026.

Rendezvous, external light (FCOM), ASYNC, rigid point · unlimited visibility · transparent · no faults · external light (FCOM) · rigid · \(n = 2\)

1. Close the gap between 3 and 6 colours Wada et al. 2026.

ASYNC with weak multiplicity detection point · unlimited visibility · transparent · no faults · weak multiplicity · \(n \ge 3\)

1. How many epochs does oblivious ASYNC gathering with weak multiplicity detection need?

Rendezvous, internal light (FSTA), ASYNC point · unlimited visibility · transparent · no faults · internal light (FSTA) · \(n = 2\)

1. Can robots with internal lights solve rendezvous in ASYNC Flocchini et al. 2016a Wada et al. 2026?

Crash faults, SSYNC point · unlimited visibility · transparent · crash faults · SSYNC · weak multiplicity · \(n \ge 3\)

1. "The maximum number of faults under which a solution is still feasible, for gathering and other tasks, has yet to be established" Agmon & Peleg 2006, in particular in ASYNC.

Crash faults, ASYNC, restricted start point · unlimited visibility · transparent · crash faults · weak multiplicity · \(n \ge 3\) · restricted start

1. Gather despite crashes in ASYNC from every solvable initial configuration, symmetric ones included, with weak multiplicity detection.

Limited visibility with a compass, rigid, ASYNC point · transparent · no faults · compass · rigid

1. Does \(O(\Delta_0)\)-epoch gathering need rigid moves, or a visibility radius larger than the connectivity range Poudel & Sharma 2021?

Limited visibility, one common axis, rigid, ASYNC point · transparent · no faults · one axis · rigid

1. Can asynchronous robots with one common axis and limited visibility gather at a point, and in \(O(\Delta_0)\) epochs? Poudel & Sharma 2021 reach only a horizontal segment of length 1, because two robots on a horizontal line, disagreeing on east and west, may swap places forever.

Limited visibility, FSYNC, disoriented point · transparent · no faults · FSYNC

1. Is \(\Omega(\Delta_0^2)\) necessary for every protocol, not only local convex-hull ones?

Fat robots, few robots, no common orientation unlimited visibility · no faults · \(n \ge 3\)

1. Gathering any number of fat robots without chirality Agathangelou et al. 2013.

Fat robots, chirality, any number unlimited visibility · no faults · chirality · \(n \ge 3\)

1. Remove the chirality assumption Agathangelou et al. 2013.

Transparent fat robots, no chirality unlimited visibility · transparent · no faults · \(n \ge 3\)

1. Gathering transparent fat robots from symmetric starts; the paper proves no general impossibility Chaudhuri & Mukhopadhyaya 2015.

Uniform circle formation

ASYNC, oblivious, disoriented point · unlimited visibility · transparent · no faults

1. Can oblivious robots without lights form a uniform circle in \(O(1)\) epochs, with rigid or non-rigid moves? Feletti et al. 2026a

Opaque robots with lights, ASYNC point · unlimited visibility · no faults · lights (LUMI) · rigid

1. What is the exact minimum number of colours for \(O(1)\)-epoch uniform circle formation in ASYNC? Feletti et al. 2026a

2. Uniform circle formation with non-rigid moves in the luminous opaque model Feletti et al. 2026a.

Convergence

Limited visibility, asynchronous point · transparent · no faults

1. Is point convergence with limited visibility solvable in full ASYNC, without perception or motion errors? Kirkpatrick et al. 2024

2. Is there a problem that separates k-ASYNC from SSYNC? Kirkpatrick et al. 2024

Linear search (cow path)

\(k\) robots on a line, Byzantine faults line · search · wireless · equal speeds

1. Determine the optimal competitive ratio \(B(k,f)\) for Byzantine search on the line; already \(B(3,1)\) is open.

Evacuation

Disk, two wireless robots of different speeds disk · two robots · wireless · no faults

1. Optimal evacuation for \(1 < v < 2.75\), for more than two robots, and face-to-face Lamprou et al. 2020.

Two robots, two exits, wireless disk · two robots · two exits · wireless · no faults · equal speeds

1. Close the gap between \(2R\) and \((1+\pi/3)R\) for two wireless robots and two exits Pattanayak et al. 2018.

Disk, search-and-fetch, two wireless robots disk · two robots · search-and-fetch · wireless · no faults

1. Lower bounds that separate wireless from face-to-face search-and-fetch Georgiou et al. 2019.

Two face-to-face robots, disk disk · two robots · no faults · equal speeds

1. Close the gap between \(3+\pi/6+\sqrt3 \approx 5.255\) and \(5.6234\) for two face-to-face robots.

Two robots with asymmetric communication, disk disk · two robots · sender/receiver · no faults · equal speeds

1. Give an explicit lower bound above \(\approx 4.826\) for sender/receiver evacuation.

Disk, priority evacuation, queen and one servant disk · two robots · priority (queen) · wireless · no faults

1. Close the gap between \(4.568\) and \(4.819\) Georgiou & Wang 2025.

Disk, weighted evacuation of two wireless robots disk · two robots · weighted · wireless · no faults · equal speeds

1. Close the gap for weighted evacuation of two wireless robots in the disk when \(w > 1\) Georgiou & Wang 2025.

Three wireless robots, disk disk · three robots · wireless · no faults · equal speeds

1. Find the optimal evacuation time for three wireless robots.

Three wireless robots, one crash fault disk · three robots · wireless · crash faults · equal speeds

1. Tight bounds for disk evacuation with one crash-faulty robot among three.

Disk, \(k\) wireless robots, \(f\) Byzantine disk · wireless · equal speeds

1. Lower bounds for evacuation of \(k\) robots with \(f\) Byzantine faults from the disk Behrouz et al. 2025.

Disk search, \(k\) wireless robots, one Byzantine disk · search · wireless · equal speeds

1. Search of the disk with \(f \ge 2\) Byzantine robots: only the crash lower bound \(1+2\pi(f+1)/k\) and evacuation upper bounds are known Georgiou et al. 2023b Behrouz et al. 2025.

Priority evacuation (queen and servants), disk disk · priority (queen) · wireless · no faults · equal speeds

1. Close the gap for priority evacuation; for one servant the bounds differ by about 0.25 (a 2024 preprint, not yet in the bibliography).

Disk, \(k\) face-to-face robots, \(f\) Byzantine disk · equal speeds

1. Lower bounds for face-to-face evacuation of the disk with Byzantine robots Behrouz et al. 2025.

Disk, \(k\) face-to-face robots, \(f\) crash faults disk · crash faults · equal speeds

1. Tight bounds for face-to-face evacuation of the disk with crash faults.

Line, weighted evacuation of two wireless robots line · two robots · weighted · wireless · no faults · equal speeds

1. Weighted evacuation with more than two robots Georgiou & Lucier 2023.

Line, weighted evacuation of two face-to-face robots line · two robots · weighted · no faults · equal speeds

1. Lower bounds for weighted evacuation of two face-to-face robots on the line Georgiou & Lucier 2023.

Line, priority evacuation, queen and one wireless servant line · two robots · priority (queen) · wireless · no faults · equal speeds

1. A lower bound for priority evacuation of a queen and one wireless servant on the line.

Line, priority evacuation, queen and one face-to-face servant line · two robots · priority (queen) · no faults · equal speeds

1. A lower bound for priority evacuation of a queen and one face-to-face servant on the line.

Line, a sender and a receiver line · two robots · sender/receiver · no faults · equal speeds

1. Close the gaps for one sender and many receivers (\(2+\sqrt5\) against \(5\)) and for many senders and one receiver (\(3\) against about \(5.681\)) Czyzowicz et al. 2021d.

Line, \(2f+1\) wireless robots, \(f\) crash faults line · wireless · crash faults · equal speeds

1. Tight bounds for evacuation with \(k = 2f+1\) crash or Byzantine robots Czyzowicz et al. 2021e.

Triangle, any number of wireless robots at the centroid triangle · wireless · no faults · equal speeds

1. The optimal evacuation time of \(k = 3, \dots, 7\) wireless robots from the centroid of the triangle.

Square, any number of wireless robots at the centre square · wireless · no faults · equal speeds

1. The optimal evacuation time of \(k\) wireless robots from the centre of the square for fixed \(k\).

Triangle, two wireless robots starting on the boundary triangle, boundary start · two robots · wireless · no faults · equal speeds

1. Face-to-face evacuation of general triangles, and wireless evacuation of obtuse triangles Georgiou & Jang 2026.

\(m\) rays, \(k = m\) wireless robots at the junction rays · wireless · no faults · equal speeds

1. Starting off the junction with \(k = m\): close \(2+\sqrt{7/3} \approx 3.528\) against \(4\) Brandt et al. 2020b.

2. Fewer robots than rays (\(1 < k < m\)): the bounds \(3+2\lfloor (m-1)/k\rfloor\) and \(1+2\tfrac{m-1}{k}(1+\tfrac{k}{m-1})^{1+(m-1)/k}\) differ Brandt et al. 2020b.

Square, two wireless robots starting on the boundary square, boundary start · two robots · wireless · no faults · equal speeds

1. Optimal evacuation of the square by \(k \ge 3\) wireless robots from a point of the boundary other than a corner.

Black hole search

Eventually emerging black hole, synchronous agents, arbitrary graphs static graph · undirected · no faults · synchronous

1. Do three synchronous agents suffice on arbitrary graphs Kaur et al. 2026a?

Eventually emerging black hole, synchronous agents, oriented ring static graph · undirected · no faults · synchronous · sense of direction · ring

1. Is one algorithm optimal in every respect at once: three agents, no knowledge of \(n\), no pebble and \(O(n)\) rounds? Left open by Bonnet et al. 2026b.

Eventually emerging black hole, asynchronous agents, oriented ring static graph · undirected · no faults · sense of direction · ring

1. How many asynchronous agents without pebbles are needed with implicit termination: between 3 and \(n\)? With two pebbles four suffice Bonnet et al. 2026b.

Dynamic graphs with whiteboards connected every round · undirected · no faults · present from the start · synchronous · whiteboards

1. With at most one missing edge per round, do four or five co-located agents suffice? Three do not Kaur et al. 2026b.

2. With scattered agents and at most one missing edge per round, do \(2\deg(v_{BH})+1\) or \(2\deg(v_{BH})+2\) agents suffice? \(2\deg(v_{BH})\) do not Kaur et al. 2026b and \(2\deg(v_{BH})+3\) do Bileski & Miller 2026.

3. With up to \(\mu\) missing edges per round, can \(O(\mu)\) co-located agents locate the black hole in polynomial time? The known algorithm with \(6\mu\) agents takes exponential time Kaur et al. 2026b.

Gathering in graphs

Labelled agents static graph · undirected · no faults · distinct IDs (eponymous) · synchronous

1. Gathering without communication when no bound on \(n\) is known.

Weakly Byzantine agents static graph · undirected · at most weak Byzantine faults · distinct IDs (eponymous) · synchronous

1. Can weakly Byzantine agents solve self-stabilizing perpetual gathering (from arbitrary memory states, all good agents eventually always at one node) with no global knowledge? Hirose et al. 2025 solve it with upper bounds on \(n\), \(k\) and \(f\) and the length of the largest label of a good agent, and leave this open.

Byzantine agents static graph · undirected · distinct IDs (eponymous) · synchronous

1. Polynomial-time Byzantine gathering with teams of size close to \(f+1\).

Exploration of dynamic graphs by teams

Connected at every step, any graph connected every round · undirected · synchronous

1. Does the algorithm with \(2m-n+1\) agents explore in polynomial time? Posed in Dobrev et al. 2020a.

1-interval-connected rings connected every round · undirected · synchronous · ring

1. With a landmark but no chirality, is \(O(n\log n)\) time necessary? Di Luna et al. 2020b

Scattering

Randomized, ASYNC point · unlimited visibility · transparent · no faults · randomized

1. Solve scattering in ASYNC without multiplicity detection: Bramas and Tixeuil call ASYNC scattering "the open problem of ASYNC scattering" Bramas & Tixeuil 2016 Bramas & Tixeuil 2017; Léchine and Tixeuil solve it with detection of multiplicity at the robot's own point and leave the plane without detection open Léchine & Tixeuil 2019.

Randomized, ASYNC, weak multiplicity detection point · unlimited visibility · transparent · no faults · weak multiplicity · randomized

1. Bound the expected time of ASYNC scattering with weak multiplicity detection.

Randomized, ASYNC, rigid, weak multiplicity detection, no vision needed point · transparent · no faults · rigid · weak multiplicity · randomized

1. Is there a polynomial bound on the expected time of blind rigid ASYNC scattering in the plane?

Pattern sequences

Oblivious, SSYNC, chirality point · unlimited visibility · transparent · no faults · SSYNC · chirality · rigid

1. Form a sequence of patterns in ASYNC with oblivious robots Das et al. 2015b.

Luminous robots, ASYNC, non-rigid, chirality point · unlimited visibility · transparent · no faults · lights (LUMI) · chirality

1. Close the gap between the colours used and the lower bound of Theorem 18 Das et al. 2020.

2. Pattern sequences with lights without chirality, with faults, or self-stabilising Das et al. 2020.

Near-gathering

ASYNC, limited visibility, one common axis point · transparent · no faults · one axis

1. Pagli, Prencipe and Viglietta conjecture that near-gathering is impossible without agreement on one axis.

SSYNC, limited visibility, disoriented point · transparent · no faults · SSYNC

1. Near-gathering in \(O(\Delta_0)\) epochs?

Mutual visibility

Finite state, SSYNC, non-rigid point · unlimited visibility · no faults · SSYNC · internal light (FSTA)

1. Solve mutual visibility with finite-state robots under ASYNC Bhagat & Mukhopadhyaya 2019.

Lights, ASYNC, rigid point · unlimited visibility · no faults · lights (LUMI) · rigid

1. Fewer colours with \(O(1)\) epochs Sharma et al. 2021a.

2. Time bounds with non-rigid moves.

Lights, ASYNC, non-rigid, one axis point · unlimited visibility · no faults · lights (LUMI) · one axis

1. Mutual visibility in non-rigid ASYNC without axis agreement, ideally with 2 colours Di Luna et al. 2017.

Lights, FSYNC, rigid, chirality point · unlimited visibility · no faults · FSYNC · lights (LUMI) · chirality · rigid

1. What is the lower bound on the number of rounds, and can chirality and crossing paths be dropped Vaidyanathan et al. 2015?

Lights, mobility faults, SSYNC, non-rigid point · unlimited visibility · crash faults · SSYNC · lights (LUMI)

1. Can mobility-fault-tolerant mutual visibility under a movement budget be solved without the common reference point and without any axis agreement Shukla et al. 2026a?

2. Does the budget-constrained algorithm extend to ASYNC Shukla et al. 2026a?

Lights, one crash, SSYNC, rigid, compass point · unlimited visibility · crash faults · SSYNC · lights (LUMI) · compass · rigid

1. Tolerating three or more crashes, and using 2 colours Aljohani & Sharma 2018.

Lights, crash faults, ASYNC, one axis point · unlimited visibility · crash faults · lights (LUMI) · one axis

1. Mutual visibility with several crashes when a crashed robot's light stops changing too, which Poudel et al. 2021 call "a major open problem".

2. Two colours in ASYNC with crashes Poudel et al. 2021.

Fat robots, ASYNC, rigid, one axis unlimited visibility · no faults · lights (LUMI) · one axis · rigid

1. Non-rigid moves, and SSYNC and ASYNC extensions of the 2-colour FSYNC algorithm Alsaedi et al. 2023a.

2. Mutual visibility of fat robots in ASYNC with non-rigid moves and no axis agreement Bhagat et al. 2024.

k-grouping

\(k\) equal groups, randomized, SSYNC point · unlimited visibility · transparent · crash faults · SSYNC · randomized

1. Partitioning in ASYNC without a common orientation, by a randomized algorithm with no extra memory.

Minimum spanning tree by agents

Arbitrary start static graph · undirected · distinct IDs (eponymous) · local communication · synchronous

1. An MST from an arbitrary start in \(O(m + n\log n)\) rounds, or fewer, with \(O(\log n)\) bits per agent and no knowledge of graph parameters.

Leader election in programmable matter

Deterministic, with chirality constant memory · strong scheduler · chirality · may move · may disconnect

1. Fast deterministic leader election under weaker (non-atomic) schedulers, and without letting the system disconnect Dufoulon et al. 2021.

Deterministic, no orientation constant memory · strong scheduler · may move

1. Deterministic leader election without chirality in linear time.

Stationary, randomized, sequential, holes allowed constant memory · sequential · randomized

1. Prove the \(O(n\log n)\) bound with high probability that Warner & Scheideler 2026a states without proof, and give a lower bound on rounds.

2. Can stationary randomized particles without a common orientation elect a unique leader on configurations with holes under the strong or the weak scheduler, which let several particles act at the same time?

Stationary, chirality, weak scheduler constant memory · chirality

1. Prove, or improve, the \(O(n^2)\)-round bound of Bazzi & Briones 2019, which the paper states without proof, and give a lower bound on rounds.

2. Elect a bounded number of leaders deterministically, without moving, under the weak scheduler and without chirality, on configurations with holes; Bazzi and Briones conjecture that it is possible Bazzi & Briones 2019.

Stationary, asynchronous, no orientation, no holes constant memory · no holes

1. Deterministic leader election in \(O(L_{out}+D)\) rounds under a weaker scheduler Dufoulon et al. 2021.

Stationary, reconfigurable circuits, synchronous, randomized constant memory · synchronous · circuits · randomized

1. Give a lower bound on the rounds needed to elect a leader with circuits; neither paper read proves one.

SILBOT with holes may move

1. Can SILBOT particles elect leaders from configurations with holes if the system may disconnect temporarily, without exterior awareness? The impossibility of D'Angelo et al. 2020 assumes that connectivity is preserved.

Shape formation in programmable matter

SILBOT, chirality chirality

1. Is line formation solvable in SILBOT when particles share just one direction instead of the full orientation Navarra & Piselli 2023b?

SILBOT, full orientation common compass · may disconnect

1. Does 1-hop visibility suffice for line formation in SILBOT Navarra & Piselli 2023b?

2. Which other shapes can SILBOT particles form Navarra & Piselli 2023b?

Coating

SILBOT, chirality, deterministic chirality

1. Coating in SILBOT without chirality Navarra & Piselli 2023a.

2. Multi-layer coating, which "seems unfeasible" in SILBOT Navarra & Piselli 2023a.

Compression

Markov chain, sequential constant memory · sequential · randomized

1. Behaviour for \(2.17 \le \lambda \le 2+\sqrt2\), and bounds on the convergence time.

Patrolling

Closed fence, one-way, distinct speeds circle · no faults

1. Close the factor \(O(\log\log k)\) between the schedule of Haeupler et al. 2019 and the bound \(\sum_i v_i\) on the one-way circle.

Closed fence, two-way, distinct speeds circle · two-way · no faults

1. What is the largest ratio between optimal schedules and the best simple strategy on the two-way circle? It lies between \(3/2\) Dumitrescu et al. 2014 and 2, since partition patrols \(\sum_i v_i/2\) and no schedule patrols more than \(\sum_i v_i\) (Proposition 2 of Czyzowicz et al. 2011).

Open fence, distinct speeds segment · two-way · no faults

1. Is computing an optimal schedule for given speeds on a segment hard?

Graphs with faulty patrollers two-way · crash faults · equal speeds

1. Is the decision version of fault-tolerant patrolling in NP? With \(k\) part of the input and integer edge lengths it is in PSPACE Czyzowicz et al. 2017e.

2. Optimal fault-tolerant patrolling of a segment when \(f \ge k/2 - 1\), and for even \(f\) Czyzowicz et al. 2017e.

3. Approximation algorithms for the optimal idle time on general graphs Czyzowicz et al. 2017e.

Network decontamination

Dynamic graphs, monotone strategies connected every round · undirected · synchronous

1. How many co-located agents are necessary and sufficient to clean every 1-interval connected dynamic graph monotonically, as a function of \(n\), \(m\) and \(D\)? \(D+2(m-n+1)\) suffice, and \(n-1\) (on \(K_{n/2,n/2}\)) and \(n\) (on wheels) can be necessary Bar et al. 2026.

Exploration by oblivious robots

Rings, ASYNC, terminating static graph · undirected · terminating · ring

1. Can four robots explore and stop on every ring of odd size \(n\) under ASYNC? Four suffice under SSYNC for odd \(n > 7\); the question is posed in Lamani et al. 2010.

2. For which pairs \((n, k)\) can \(k\) robots explore an \(n\)-node ring Flocchini et al. 2013? In particular, is exploration impossible whenever \(\gcd(n, k) > 1\) and \(k < n\), as conjectured in Lamani et al. 2010? Impossibility is proved only when \(k\) divides \(n\) Flocchini et al. 2013, and for \(k = 4\) with even \(n\) Lamani et al. 2010.

3. What is the minimum number of robots when \(n\) is a multiple of 5? From model checking on rings of fewer than 18 nodes, Bérard et al. conjecture that the algorithm of Flocchini et al. 2013 is correct for every odd \(k\) with \(5 \le k < 17\) from initial configurations with at most one axis of symmetry Bérard et al. 2016; the lower bounds use more symmetric starts.

Rings, SSYNC, terminating static graph · undirected · SSYNC · terminating · ring

1. What is the minimum number of robots under SSYNC when \(n\) is a multiple of 10 (four and five robots are impossible)? This is the SSYNC case of the characterisation of solvable pairs \((n, k)\) asked for in Flocchini et al. 2013.

Rings, probabilistic, SSYNC, terminating static graph · undirected · private coins · SSYNC · terminating · ring

1. How many moves (or rounds) do four probabilistic robots need to explore a ring of \(n\) nodes and stop, and how does the time decrease when more robots are used? Posed in Devismes et al. 2013, where termination is only shown to be finite.

Rings, ASYNC, exclusive perpetual static graph · undirected · exclusive perpetual · ring

1. What is the minimum number of robots for exclusive perpetual exploration of a ring whose size is a multiple of 3, from every configuration without towers?

2. Would coin flips help in the cases where deterministic exclusive perpetual exploration is impossible? Posed in Blin et al. 2010.

3. What is the largest team that can explore exclusively and perpetually from every configuration without towers? Blin et al. 2010 claim \(n - 5\) robots for odd \(k \ge 7\) with \(k \nmid n\), but an SMT check found collisions in their algorithm for 7 and 9 robots on rings of \(k + 5\) nodes under FSYNC Sangnier et al. 2020.

Exploration by luminous robots

Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) static graph · undirected · grid · terminating · luminous · FSYNC · no faults

1. How many robots are needed for terminating grid exploration under FSYNC with \(\varphi = 1\) and no chirality: three or four?

Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) static graph · undirected · grid · terminating · luminous · no faults

1. Close the gap between three and six robots for terminating grid exploration under ASYNC with \(\varphi = 1\) and no chirality Nagahama et al. 2022.

Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) static graph · undirected · grid · perpetual · luminous · \(\varphi=2\) · chirality · no faults

1. Can two luminous robots with common chirality and \(\varphi = 2\) explore a finite grid perpetually under ASYNC (or SSYNC)?

Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) static graph · undirected · grid · perpetual · luminous · \(\varphi=2\) · no faults

1. Is there an optimal ASYNC algorithm (three robots, \(\varphi = 2\), no chirality) for opaque robots? Posed in Bramas et al. 2026a.

2. Can two robots without chirality explore a grid perpetually with \(\varphi \ge 2\) under FSYNC? Rauch et al. 2021 state that they cannot for every finite \(\varphi\), but prove it for \(\varphi = 1\).

Grids, ASYNC, perpetual, chirality, \(\varphi = 1\) (exclusive) static graph · undirected · grid · perpetual · luminous · chirality · no faults

1. Is perpetual grid exploration with \(\varphi = 1\) solvable under ASYNC when robots may share nodes (form towers)? Terminating exploration is, with three robots and three colours Nagahama et al. 2022.

Grids, ASYNC, perpetual, no chirality, \(\varphi = 3\) static graph · undirected · grid · perpetual · luminous · \(\varphi=3\) · no faults

1. Can two robots without chirality explore a grid perpetually with \(\varphi \ge 2\) under FSYNC? Rauch et al. 2021 state that they cannot for every finite \(\varphi\), but prove it for \(\varphi = 1\).

Rings, FSYNC, perpetual, up to \(f\) crashes static graph · undirected · ring · perpetual · luminous · FSYNC · at most crash faults

1. With \(f + 2\) robots under FSYNC, how many colours are necessary for crash-tolerant perpetual ring exploration? The best algorithm uses \(3f + 2\) Ooshita et al. 2024.

Rings, ASYNC, perpetual, \(\varphi = 1\) static graph · undirected · ring · perpetual · luminous · no faults

1. Can three oblivious robots (\(c = 1\)) with \(\varphi = 1\) explore a ring perpetually under SSYNC or ASYNC, or are two colours necessary?

Rings, FSYNC, terminating, \(\varphi = 1\) static graph · undirected · ring · terminating · luminous · FSYNC · no faults

1. Characterise the initial configurations of three robots with \(c \ge 3\) colours from which terminating exploration of a ring is solvable under FSYNC with \(\varphi = 1\) (with two colours no universal algorithm exists Ooshita & Tixeuil 2022).

Rings, ASYNC, terminating, \(\varphi = 1\) static graph · undirected · ring · terminating · luminous · no faults

1. Does any task separate SSYNC from ASYNC for myopic luminous robots on rings? The known exploration bounds coincide under both Ooshita & Tixeuil 2022.

Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) static graph · undirected · torus · perpetual · luminous · FSYNC · \(\varphi=2\) · no faults

1. Can four oblivious robots with \(\varphi = 2\) explore a torus perpetually without chirality?

Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) static graph · undirected · torus · perpetual · luminous · FSYNC · no faults

1. Can three robots with two colours and \(\varphi = 1\) explore a torus perpetually without common chirality?

Triangular grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) static graph · undirected · triangular grid · perpetual · luminous · FSYNC · no faults

1. Is there a proof of perpetual triangular-grid exploration by two robots with \(\varphi = 1\) for self-inconsistent robots, or with two colours?

Exploration of recolourable graphs

Recolourable nodes, oblivious agent, any graph static graph · undirected · neighbour colours · recolourable · uniform \(c_0\)

1. Is the colour complexity of recolourable exploration of arbitrary graphs 4, 5 or 6 Takahashi et al. 2025 Hiraoka et al. 2026?

2. Give a proof of the four-colour lower bound without computer assistance, or for a single graph Hiraoka et al. 2026.

3. How many moves does a constant-colour algorithm need on general graphs? No bound is known; for graphs whose blocks are cliques or triangle-free, five colours and \(O(n\Delta)\) moves suffice Hiraoka et al. 2026.

4. How many colours suffice if the agent has a constant number of bits, or even one bit, of memory, or may move at random Böckenhauer et al. 2023 Takahashi et al. 2025?

5. Does forbidding recolouring back to \(c_0\) change the colour complexity, or only the algorithms Takahashi et al. 2025?

Recolourable nodes on cacti static graph · undirected · neighbour colours · recolourable · uniform \(c_0\) · cactus

1. Is four colours enough for φ-free graphs, or for graphs of maximum degree three? Both lie between 4 and 5 Hiraoka et al. 2026.

Once-colourable nodes, any graph static graph · undirected · neighbour colours · colour once · uniform \(c_0\)

1. For graphs of circumference \(\mathrm{circ}(G) \le g\), close the gap between \(\min(2g-2, n)\) and \(\min(2g, n)\) colours Böckenhauer et al. 2023.

Once-colourable nodes, \(n\) known static graph · undirected · neighbour colours · colour once · uniform \(c_0\) · \(n\) known

1. Is the colour complexity with known \(n\) equal to \(n-2\) or \(n-1\) Böckenhauer et al. 2023?

Rotor-router: a pointer in every node static graph · undirected · ports, no entry port · recolourable · perpetual

1. For which graphs (other than paths) is the rotor-router exactly time-optimal among oblivious agents without the entry port Menc et al. 2017?

Rotor-router with pointers set by a designer static graph · undirected · ports, no entry port · recolourable · designer's colours · perpetual

1. How few moves does a rotor-router with designer pointers need to visit every node, as opposed to locking in? In Hamiltonian graphs the pointers can follow a Hamiltonian cycle Bampas et al. 2017.

Label-guided: colours fixed by a designer static graph · undirected · ports + entry port · finite automaton · designer's colours · stop

1. Is there a 1-bit (two-colour) labeling with which a finite automaton explores every graph Cohen et al. 2008?

Label-guided, oblivious agent static graph · undirected · ports + entry port · designer's colours · perpetual

1. How many designer colours does an oblivious agent need to explore all graphs of maximum degree \(\Delta\) Cohen et al. 2008?

Uniform deployment on a ring

Oriented ring, asynchronous, oblivious point · unlimited visibility · transparent · no faults · chirality

1. Is knowledge of \(d\) necessary for exact deployment on an oriented ring? Which capabilities allow asynchronous exact deployment on unoriented rings? Flocchini et al. 2008b

Search with segment visibility

Two robots, unknown distance two robots · no faults · equal speeds

1. Determine the optimal competitive ratio of two robots that do not know \(d\): it lies between \(\sqrt3+\pi/6+\sqrt{17}/4 \approx 3.2864\) and \(\approx 8.9285\) Kranakis 2026.

2. Do asymmetric, non-antipodal or non-spiral trajectories beat \(\approx 8.9285\)? The antipodal spirals see only along a diameter through the origin, while a segment between two moving robots can sweep chords that miss it Kranakis 2026.

Partitioning

Exactly \(n/k\) robots at each fixed point point · unlimited visibility · transparent · no faults · one axis

1. Partitioning into \(k\) groups of size \(n/k\) at points chosen by the robots (no fixed points given).

Scattering of particles

SILBOT nothing assumed on any axis

1. Is scattering solvable in SILBOT with its original 2-hop view under adversarial activation? Navarra et al. 2025 leave it open.

SILBOT with event-driven activation event-driven

1. Bound the rounds and moves of scattering under event-driven activation Navarra et al. 2025.

2. Scattering with obstacles: unsolvable deterministically with a 1-hop view even under a synchronous scheduler (Theorem 7 of Navarra et al. 2025); which extra capability (chirality, a 2-hop view, randomised choices) makes it solvable?

Separation of coloured particles

Markov chain, sequential constant memory · sequential · randomized

1. Bounds on the convergence (mixing) time.

Centralised transformations of modular robots

Rotation only nothing assumed on any axis

1. What is the complexity of connectivity-preserving transformability with rotations alone? The paper leaves it open (Section 7) Michail et al. 2019.

Rotation and sliding rotation + sliding

1. Prove the suspected \(\Omega(n\log n)\) lower bound for universal transformations with line pushing Almethen et al. 2020.

2. Distributed universal transformations with line pushing Almethen et al. 2020.

Online exploration of weighted graphs

Arbitrary weighted graphs static graph · undirected · labelled nodes

1. Is there a deterministic algorithm with a constant competitive ratio (Kalyanasundaram and Pruhs Kalyanasundaram & Pruhs 1994, as reported by Baligács 2026)?

2. Is there an \(o(\log n)\)-competitive algorithm? Blocking with parameter \(\chi\) (their \(\delta\)) is \(\Omega(\log n)\)-competitive for \(\chi = o(\log n/\log\log n)\) and for \(\chi = \Omega(\log n)\), and \(\Omega(\log n/\log\log n)\)-competitive for every \(\chi\); the range in between is open Baligács et al. 2026a.

3. Does randomization lower the competitive ratio on general graphs? It does on cycles Baligács et al. 2026b.

Known graph, weight estimates static graph · undirected · labelled nodes · weight estimates

1. Does every graph admit a \(\tfrac{1+\vartheta}{2}\)-competitive algorithm when all weights are announced in the same interval \([1, \vartheta]\) with \(\vartheta \le 2\)? Conjectured by Gehnen et al. 2025.

Graphs excluding a fixed minor static graph · undirected · labelled nodes · \(H\)-minor-free

1. How does the best constant depend on the excluded minor \(H\), and on the genus for graphs of bounded genus Baligács et al. 2026a?

Planar graphs static graph · undirected · labelled nodes · planar

1. Close 4 against 16 on planar graphs.

Weighted cycles, randomized agent static graph · undirected · labelled nodes · private coins · ring

1. Determine the randomized competitive ratio on cycles: \(1.1155\) against \(1.3144\) Baligács et al. 2026b.

2. Must an optimal randomized algorithm on cycles be forward-greedy Baligács et al. 2026b?

Gathering by oblivious robots on graphs

Rings, round robin, no multiplicity detection static graph · undirected · no faults · ring · sequential · round robin

1. Which sequential schedulers between round robin and an arbitrary sequential scheduler still allow gathering on rings without multiplicity detection? Navarra & Piselli 2025 ask about other sequential schedulers; on graphs that are not vertex-transitive, a new order in every epoch suffices Cicerone et al. 2025d.

Rings, ASYNC, weak multiplicity detection static graph · undirected · no faults · ring · weak detection · dispersed start

1. Even \(k\): which symmetric starts whose axis passes through a node can be gathered? Left open by Klasing et al. 2008; four robots on rings of seven and nine nodes cannot gather from some of them D'Emidio et al. 2018, and the proofs do not extend to other ring sizes. Later ring papers listed in Cicerone et al. 2025d were not read here.

Complete graphs, FSYNC, strong multiplicity detection static graph · undirected · no faults · complete graph · strong detection · dispersed start · FSYNC

1. Does every algorithm need \(\Omega(\log k)\) epochs on complete graphs for infinitely many \(k\), without assuming infinitely many Fibonacci primes? The lower bound of Cicerone et al. 2021b uses \(k = F_\ell\) robots and \(F_{\ell-1}\) empty nodes, solvable only when \(F_\ell\) is prime.

Graphs that are not vertex-transitive, round robin static graph · undirected · no faults · not vertex-transitive · sequential · round robin

1. Can robots gather in \(O(d)\) epochs on every graph that is not vertex-transitive and has no terminal orbit? Asked in Cicerone et al. 2025d.

Finite grids, ASYNC, no multiplicity detection static graph · undirected · no faults · finite grid · dispersed start

1. How many epochs does gathering on finite grids without multiplicity detection take?

Broadcast by agents in dynamic graphs

Dynamic graph, any topology connected every round · undirected · distinct IDs (eponymous) · local communication · synchronous · dispersed start

1. Which graph property determines the least number of agents that solve broadcast on a graph \(G\)? Edge density, edge connectivity and the number of redundant edges do not Moses Jr. et al. 2025; is there an analogue of dismantlability, which characterises cop-win graphs? Moses Jr. et al. 2026

2. How many rounds do the agents need when they win, as a function of \(n\) and \(D\)? Only lower bounds of order \(D\) are known Moses Jr. et al. 2026.

3. Can broadcast be solved with weaker agents than global visibility, for example agents that see only the source agent? Das et al. 2026b

Dynamic hypercubes connected every round · undirected · distinct IDs (eponymous) · local communication · synchronous · dispersed start · hypercube

1. How many agents are needed on \(Q_j\) for \(j \ge 4\): \(n/2\), \(n - 3\), or in between? Das et al. 2026b

Dynamic grids connected every round · undirected · distinct IDs (eponymous) · local communication · synchronous · dispersed start · grid

1. Close the gap between \((\sqrt n - 1)^2 + 1\) and \(n - 3\) agents on the \(\sqrt n \times \sqrt n\) grid Das et al. 2026b.

Search for a moving target

Line, two face-to-face robots, away, \(u\) known line · two robots · away · speed known · no faults · equal speeds

1. Is \((3+u)^2/(1-u)^2\) optimal for two face-to-face robots for every \(u \in (0,1)\), as it is for one robot?

Line, a sender and a receiver, away, \(u\) known line · two robots · away · speed known · sender/receiver · no faults · equal speeds

1. Is \((\sqrt{u^2-2u+2}+1)/(\sqrt{u^2-2u+2}-1)\) optimal for a sender and a receiver for \(u > 0\)?

One robot, line, target moving away, speed known line · one robot · away · speed known · no faults · equal speeds

1. Tight bounds when the robot does not know whether the target moves toward or away from the origin Coleman et al. 2022.

One robot, line, target moving away, \(d\) known line · one robot · away · distance known · no faults · equal speeds

1. Determine the lower-order terms in the exponent: the bounds differ by a factor \((1-u)^{-o(1)}\) Coleman et al. 2026a.

One robot, line, target moving away, nothing known line · one robot · away · no faults · equal speeds

1. Tight bounds when neither \(d\) nor \(u\) is known Coleman et al. 2026a; the upper bound grows with \(d\), the lower bounds do not.

\(m\) rays, a sender and a receiver, away, \(u\) known two robots · away · speed known · sender/receiver · no faults · equal speeds

1. For even \(m \ge 4\), can a sender and a receiver beat two face-to-face robots, as they do on the line?

Collision-free exploration

Two agents sensing presence, with coloured pebbles static graph · undirected · synchronous · two agents · the team · bound on \(n\) · presence · pebbles

1. Do two colours suffice on every graph Das et al. 2025a?

2. How fast can two agents explore with three colours Das et al. 2025a?

Two agents, anonymous graphs, vision of radius 2 static graph · undirected · synchronous · two agents · bound on \(n\) · radius 2

1. Can two agents explore without collisions as fast as one agent explores alone? Asked by Bhagat & Pelc 2025; Papin 2026 claims a constant factor.

2. For which number of agents below \(n\) is collision-free exploration of anonymous graphs feasible, and with which vision radius Bhagat & Pelc 2025?

Labelled graphs, no knowledge, any number of agents static graph · undirected · labelled nodes · synchronous · simultaneous start

1. Close \(O(n^5\log n)\) against \(\Omega(n^2)\) for agents without a map on graphs with labelled nodes.

Deciding graph properties by mobile agents

Any number of agents static graph · undirected · distinct IDs (eponymous) · local communication · synchronous

1. What is the least information about the number of agents that lets several agents reconstruct the whole configuration? Posed in Fraigniaud & Pelc 2017.

One agent static graph · undirected · distinct IDs (eponymous) · local communication · synchronous · one agent

1. Give a combinatorial characterisation of the problems that a lone agent decides. Posed in Fraigniaud & Pelc 2017.

2. Is it decidable whether a lone agent can decide a given problem: is there a Turing machine that, given a Turing machine deciding membership in \(\Pi\), decides whether a lone agent can decide \(\Pi\)? Posed in Fraigniaud & Pelc 2017.

One agent that knows \(n\) static graph · undirected · distinct IDs (eponymous) · local communication · synchronous · one agent · knows \(n\)

1. Is it decidable whether a lone agent that knows \(n\) can decide a given problem? Posed in Fraigniaud & Pelc 2017.

Any number of agents, with certificates static graph · undirected · distinct IDs (eponymous) · local communication · synchronous · verify

1. Do certificates that may depend on the agents' identifiers verify more problems? Raised in Bampas & Ilcinkas 2018.

2. Which problems become verifiable under the promise that there are at most two agents? Raised in Bampas & Ilcinkas 2018.

Delivery by energy-constrained agents

Arbitrary graphs static graph · undirected

1. What is the complexity of delivering several messages at once, for instance on paths? Raised in Bärtschi et al. 2020.

Paths static graph · undirected · path

1. Is there a pseudo-polynomial algorithm for delivery on a path? Posed in Chalopin et al. 2014.

2. Find good resource-augmented planners for delivery on a path. Posed in Chalopin et al. 2014.

Paths, equal budgets static graph · undirected · path · equal budgets

1. Is delivery with equal budgets between two nodes of a tree NP-hard or polynomial? Posed in Anaya et al. 2016 and again in Chalopin et al. 2013; Chalopin et al. 2021 states that on trees delivery is known to be weakly NP-hard, without a reference, in a paper about equal budgets.

Arbitrary graphs, equal budgets static graph · undirected · equal budgets

1. Is there a constant \(c > 1\) such that the smallest equal budget cannot be approximated within \(c\) in polynomial time unless P = NP? Chalopin et al. 2021 notes that no lower bound is known.

Planar graphs, equal budgets static graph · undirected · planar · equal budgets

1. Is there an inapproximability bound for the smallest equal budget, already on planar graphs? No lower bound above 1 is known for any graph class Chalopin et al. 2021.