Mobility Matters
What is known, what is tight, and what is open, under which assumptions.
AI use Claude (Anthropic) was used in cataloguing the problems.
How the problems evolved
Each year lists the problems first posed then (highlighted) and the papers that introduced a setting, gave the current best result, or proved a lower bound, dated by their first appearance (usually the conference version). The logical view arranges the same problems by reduction; the two orders can disagree, and where a derived problem was posed before its logical parent the entry says so.
1950s
1951
Mobile agents on graphs · Exploration
Graph exploration by a single agent is posed in Shannon 1951
Shannon's maze-solving mouse Theseus (first prototype 1950) explored a \(5\times5\) grid with constant memory per cell Disser et al. 2019; the first impossibility theorem for finite automata is Budach's Budach 1978.
1960s
1964
Search in geometric domains · Search, evacuation and patrolling
Linear search (cow path) is posed in Beck 1964
Bellman posed the problem in 1963 and Beck analysed it in 1964; computer scientists rediscovered it in the late 1980s as the cow-path problem Kupavskii & Welzl 2018.
1970s
1979
1990s
1990
1991
Mobile agents on graphs · Exploration
Map construction is posed in Dudek et al. 1991
Dudek, Jenkin, Milios and Wilkes framed robotic exploration as graph construction.
In the logical view: strengthening of Graph exploration by a single agent, which was posed earlier (1951).
- Dudek et al. 1991 — Map construction: One agent with a marker current best
1993
- Baeza-Yates et al. 1993 — Linear search (cow path): One robot on a line current best, One robot on a line lower bound, One robot on \(m\) rays current best, One robot on \(m\) rays lower bound
- Kao et al. 1993 — Linear search (cow path): One randomized robot on a line current best, One randomized robot on a line lower bound
1998
1999
Mobile robots in the plane · Formation problems
Pattern formation is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita characterised the patterns that anonymous robots can form in terms of their initial configuration.
Mobile robots in the plane · Formation problems
Gathering is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita gave an algorithm "moving the robots to a single point in finite steps" and showed that two oblivious robots cannot meet in SSYNC.
In the logical view: special case of k-grouping, but was posed before it (2007).
Mobile robots in the plane · Formation problems
Convergence is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita gave algorithms for converging to a point and for reaching a point; Ando et al. treated limited visibility the same year Ando et al. 1999.
- Ando et al. 1999 — Convergence: Limited visibility, SSYNC, rigid moves current best
2000s
2001
Mobile agents on graphs · Exploration
Black hole search is posed in Dobrev et al. 2001
Dobrev, Flocchini, Prencipe and Santoro introduced black hole search in rings (DISC 2001) and in arbitrary networks (PODC 2002) Dobrev et al. 2006.
In the logical view: variant of Collaborative exploration, but was posed before it (2004).
- Flocchini et al. 2001 — Gathering: Limited visibility with a compass, ASYNC current best, Limited visibility with a compass, ASYNC lower bound
- Dobrev et al. 2001 — Black hole search: Asynchronous agents with whiteboards in a ring current best, Asynchronous agents with whiteboards in a ring lower bound
2002
Mobile robots in the plane · Formation problems
Circle formation is posed in Défago & Konagaya 2002
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Exploration
Network decontamination is posed in Barrière et al. 2002
Capture of an intruder by mobile agents (SPAA 2002).
- Diks et al. 2002 — Graph exploration by a single agent: Trees, perpetual exploration current best, Trees, perpetual exploration lower bound, Trees, exploration with stop lower bound, Trees, exploration with return introduced, Trees, exploration with return lower bound
- Défago & Konagaya 2002 — Circle formation: Circle formation, SSYNC introduced
- Dobrev et al. 2002 — Black hole search: Asynchronous agents with whiteboards current best, Asynchronous agents with whiteboards lower bound, Whiteboards and sense of direction current best, Whiteboards and sense of direction lower bound, Whiteboards and a map current best, Whiteboards and a map lower bound, Tokens and a map lower bound
- Barrière et al. 2002 — Network decontamination: Trees current best
2003
Mobile agents on graphs · Exploration
Rendezvous is posed in Dessmark et al. 2003
Deterministic rendezvous of labelled agents in arbitrary graphs was posed by Dessmark, Fraigniaud and Pelc at ESA 2003. Rendezvous itself is older (randomized search games); the catalogue covers the deterministic line Pelc 2019.
In the logical view: subproblem of Graph exploration by a single agent, which was posed earlier (1951).
- Dessmark et al. 2003 — Rendezvous: Labelled agents, arbitrary finite graphs introduced, Labelled agents, arbitrary finite graphs lower bound, Labelled agents in trees current best, Labelled agents in trees lower bound, Labelled agents in rings, simultaneous start current best, Labelled agents in rings, simultaneous start lower bound
- Cieliebak et al. 2003 — Gathering: ASYNC with weak multiplicity detection current best
- Yanovski et al. 2003 — Exploration of recolourable graphs: Rotor-router: a pointer in every node current best
2004
Mobile agents on graphs · Exploration
Collaborative exploration is posed in Fraigniaud et al. 2004
Collective tree exploration was posed at LATIN 2004 (journal version 2006).
Mobile robots in the plane · Symmetry breaking and spreading
Flocking is posed in Gervasi & Prencipe 2004
Coordination without communication: the flocking problem.
- Fraigniaud et al. 2004 — Graph exploration by a single agent: Arbitrary graphs, perpetual exploration current best, Arbitrary graphs, perpetual exploration lower bound
- Fraigniaud & Ilcinkas 2004 — Graph exploration by a single agent: Directed graphs, one pebble current best, Directed graphs, one pebble lower bound
- Fraigniaud et al. 2004 — Collaborative exploration: Trees, complete communication introduced, Trees, communication by whiteboards only current best, Trees, no communication current best, Trees, no communication lower bound
- Cohen & Peleg 2004 — Convergence: ASYNC, unlimited visibility current best
- Gervasi & Prencipe 2004 — Flocking: Oblivious robots following a leader current best
2005
- Reingold 2005 — Graph exploration by a single agent: Exploration with stop when \(n\) is known current best
- Fraigniaud et al. 2005 — Graph exploration by a single agent: Exploration with stop and one pebble current best
- Fraigniaud et al. 2005 — Graph exploration by a single agent: Exploration with stop and one pebble lower bound
- Cohen et al. 2005 — Graph exploration by a single agent: Node labels chosen by the designer current best; Exploration of recolourable graphs: Label-guided: colours fixed by a designer current best, Label-guided: colours fixed by a designer lower bound, Label-guided, oblivious agent lower bound
- Fleischer & Trippen 2005 — Graph exploration by a single agent: Directed graphs with labelled nodes current best
- De Marco et al. 2005 — Rendezvous: Asynchronous labelled agents introduced
- Prencipe 2005 — Gathering: No multiplicity detection, SSYNC lower bound, Gathering, full lights, SSYNC, no multiplicity detection lower bound, Gathering, full lights, ASYNC, no multiplicity detection lower bound
- Klasing et al. 2005 — Black hole search: Synchronous agents with a map current best, Synchronous agents with a map lower bound
- Flocchini et al. 2005 — Network decontamination: Hypercubes current best, Hypercubes lower bound
2006
Mobile robots in the plane · Formation problems
Uniform circle formation is posed in Dieudonné et al. 2006
The first deterministic solution (SSS 2006); circle formation with convergence towards uniformity predates it Défago & Konagaya 2002.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile robots in the plane · Symmetry breaking and spreading
Uniform deployment on a ring is posed in Flocchini et al. 2006
Self-deployment of mobile sensors on a ring (ALGOSENSORS 2006).
- Ilcinkas 2006 — Graph exploration by a single agent: Port numbers chosen by the designer (periodic exploration) introduced
- Agmon & Peleg 2006 — Gathering: Crash faults, SSYNC introduced, Byzantine faults, SSYNC lower bound, Byzantine faults, FSYNC current best
- Czyzowicz et al. 2006 — Gathering: Fat robots, few robots, no common orientation current best
- Dieudonné et al. 2006 — Uniform circle formation: SSYNC, oblivious introduced
- Czyzowicz et al. 2006 — Black hole search: Synchronous agents with a map introduced
- Flocchini et al. 2006 — Uniform deployment on a ring: Oriented ring, asynchronous, oblivious current best, Oriented ring, asynchronous, oblivious lower bound
2007
Mobile agents on graphs · Exploration
Treasure hunt is posed in Ta-Shma & Zwick 2007
Ta-Shma and Zwick introduced the deterministic treasure hunt problem at SODA 2007, as a variant of rendezvous in which one agent never moves.
In the logical view: subproblem of Graph exploration by a single agent, which was posed earlier (1951).
Mobile robots in the plane · Symmetry breaking and spreading
Leader election in the plane is posed in Dieudonné et al. 2013
Posed for disoriented robots at OPODIS 2007 (Dieudonné and Petit); characterised in Dieudonné et al. 2013.
Mobile robots in the plane · Formation problems
k-grouping is posed in Efrima & Peleg 2007
Splitting a swarm into a given number of groups was introduced at SIROCCO 2007, under the name partitioning. No paper titled "k-grouping" was found.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Exploration
Exploration by oblivious robots is posed in Flocchini et al. 2007
Ring exploration by asynchronous oblivious robots (OPODIS 2007).
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
- Ambühl et al. 2007 — Graph exploration by a single agent: Trees, exploration with stop current best, Trees, exploration with return current best
- Ta-Shma & Zwick 2007 — Treasure hunt: Anonymous finite graphs introduced; Rendezvous: Labelled agents, arbitrary finite graphs current best
- Xin 2007 — Treasure hunt: Anonymous finite graphs current best
- Das et al. 2007 — Map construction: Identical agents with whiteboards current best, Identical agents with whiteboards lower bound
- Efrima & Peleg 2007 — k-grouping: \(k\) groups of equal size current best, \(k\) equal groups, no common orientation, deterministic lower bound, \(k\) equal groups, randomized, SSYNC current best
- Ilcinkas et al. 2007 — Network decontamination: Unknown graphs, monotone strategies current best, Unknown graphs, monotone strategies lower bound
- Flocchini et al. 2007 — Exploration by oblivious robots: Rings, exploration with stop introduced, Rings, exploration with stop lower bound
2008
- Fraigniaud & Pelc 2008 — Rendezvous: Anonymous agents in trees, simultaneous start current best, Anonymous agents in trees, simultaneous start lower bound
- Flocchini et al. 2008 — Pattern formation: ASYNC, no agreement on coordinates introduced, ASYNC, no agreement on coordinates lower bound, ASYNC with one common axis current best, ASYNC with one common axis lower bound, ASYNC with a common compass current best
- Défago & Souissi 2008 — Circle formation: Circle formation, SSYNC current best
- Flocchini et al. 2008 — Black hole search: Tokens and a map current best
2009
Mobile robots in the plane · Symmetry breaking and spreading
Scattering is posed in Dieudonné & Petit 2009
Dieudonné and Petit showed scattering is deterministically impossible and gave a randomized solution (preprint 2007).
- Czyzowicz et al. 2009 — Graph exploration by a single agent: Port numbers chosen by the designer (periodic exploration) current best, Port numbers chosen by the designer (periodic exploration) lower bound
- Dieudonné & Petit 2009 — Scattering: Randomized, SSYNC, strong multiplicity detection introduced, Randomized, SSYNC, strong multiplicity detection lower bound
2010s
2010
Mobile robots in the plane · Formation problems
Pattern sequences is posed in Das et al. 2010
Introduced at PODC 2010.
In the logical view: generalisation of Pattern formation, which was posed earlier (1999).
- Czyzowicz et al. 2010 — Rendezvous: Anonymous agents: memory current best, Anonymous agents: memory lower bound
- Dieudonné et al. 2010 — Pattern formation: ASYNC with common chirality current best
- Chaudhuri & Mukhopadhyaya 2010 — Gathering: Transparent fat robots, no chirality introduced
- Chalopin et al. 2010 — Map construction: One agent, no marking current best
- Clement et al. 2010 — Scattering: Randomized, SSYNC, strong multiplicity detection current best
- Izumi et al. 2010 — Scattering: Limited visibility, connectivity preserving current best, Limited visibility, connectivity preserving lower bound
- Das et al. 2010 — Pattern sequences: Oblivious, SSYNC, chirality current best
- Lamani et al. 2010 — Exploration by oblivious robots: Rings, exploration with stop current best, Rings, exploration with stop lower bound
2011
Search in geometric domains · Search, evacuation and patrolling
Patrolling is posed in Czyzowicz et al. 2011
Boundary patrolling by agents with distinct speeds (ESA 2011).
- Guilbault & Pelc 2011 — Rendezvous: Asynchronous anonymous agents current best
- Degener et al. 2011 — Gathering: Limited visibility, FSYNC, disoriented introduced
- Katreniak 2011 — Convergence: Limited visibility, asynchronous introduced
- Czyzowicz et al. 2011 — Patrolling: Open fence, distinct speeds introduced
2012
Mobile agents on graphs · Exploration
Gathering in graphs is posed in Dieudonné et al. 2012
Gathering many agents in arbitrary graphs grew out of two-agent rendezvous; the Byzantine version was posed at SODA 2012.
In the logical view: generalisation of Rendezvous, which was posed earlier (2003).
Mobile robots in the plane · Formation problems
Near-gathering is posed in Pagli et al. 2012
Introduced at SIROCCO 2012.
In the logical view: relaxation of Gathering, which was posed earlier (1999).
- Dieudonné & Pelc 2012 — Graph exploration by a single agent: Exploration with stop, nothing known lower bound
- Das et al. 2012 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid introduced
- Viglietta 2012 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid lower bound
- Chaudhuri & Mukhopadhyaya 2012 — Gathering: Transparent fat robots, no chirality current best; Leader election in the plane: Transparent fat robots, no chirality current best, Transparent fat robots, no chirality lower bound
- Balamohan et al. 2012 — Black hole search: Tokens, no map current best, Tokens, no map lower bound
- Dieudonné et al. 2012 — Gathering in graphs: Weakly Byzantine agents current best, Weakly Byzantine agents lower bound, Byzantine agents introduced, Byzantine agents lower bound
- Pagli et al. 2012 — Near-gathering: ASYNC, limited visibility, one common axis current best
- Kawamura & Kobayashi 2012 — Patrolling: Open fence, distinct speeds lower bound
- Devismes et al. 2012 — Exploration by oblivious robots: Grids, exploration with stop current best, Grids, exploration with stop lower bound
2013
- Ilcinkas & Wade 2013 — Graph exploration by a single agent: Dynamic rings current best, Dynamic rings lower bound
- Dereniowski et al. 2013 — Collaborative exploration: Large teams, complete communication current best, Large teams, complete communication lower bound, Large teams, local communication current best, Large teams, local communication lower bound
- Dieudonné et al. 2013 — Rendezvous: Asynchronous labelled agents current best
- Flocchini et al. 2013 — Gathering: Two robots, SSYNC lower bound, Rendezvous, external light (FCOM), SSYNC current best, Rendezvous, external light (FCOM), ASYNC, non-rigid current best, Rendezvous, external light (FCOM), ASYNC, rigid introduced, Rendezvous, internal light (FSTA), SSYNC, non-rigid current best, Rendezvous, internal light (FSTA), SSYNC, rigid introduced
- Agathangelou et al. 2013 — Gathering: Fat robots, chirality, any number current best
- Dobrev et al. 2013 — Black hole search: Tokens, no map introduced
- Dieudonné & Pelc 2013 — Gathering in graphs: Anonymous agents current best, Anonymous agents lower bound
- Dieudonné et al. 2013 — Leader election in the plane: Disoriented robots, with or without chirality current best, Disoriented robots, with or without chirality lower bound
- Datta et al. 2013 — Exploration by luminous robots: Rings, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, oblivious, FSYNC, terminating, \(\varphi = 1\) current best, Rings, oblivious, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, oblivious, ASYNC, terminating, \(\varphi = 1\) lower bound
2014
Search in geometric domains · Search, evacuation and patrolling
Evacuation is posed in Czyzowicz et al. 2014
Czyzowicz et al. posed evacuation of \(k\) robots from a disk through an unknown exit on its boundary at DISC 2014.
In the logical view: generalisation of Linear search (cow path), which was posed earlier (1964).
Mobile robots in the plane · Formation problems
Mutual visibility is posed in Di Luna et al. 2017
Introduced at CCCG 2014 for oblivious robots and at SSS 2014 for robots with lights Di Luna et al. 2014; journal version Di Luna et al. 2017.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Programmable matter · Self-organising particle systems
Coating is posed in Derakhshandeh et al. 2017
Infinite object coating appeared as an arXiv preprint in 2014; universal coating in Derakhshandeh et al. 2017.
- Miller & Pelc 2014 — Treasure hunt: Treasure hunt with advice current best, Treasure hunt with advice lower bound
- Flocchini et al. 2014 — Circle formation: Circle formation current best; Uniform circle formation: ASYNC, oblivious, disoriented current best, ASYNC, oblivious, disoriented lower bound
- Czyzowicz et al. 2014 — Evacuation: Two wireless robots, disk current best, Two wireless robots, disk lower bound, Two face-to-face robots, disk introduced, Three wireless robots, disk current best, Three wireless robots, disk lower bound, Three face-to-face robots, disk current best, Three face-to-face robots, disk lower bound, Many wireless robots, disk current best, Many wireless robots, disk lower bound, Many face-to-face robots, disk current best, Many face-to-face robots, disk lower bound
- Das et al. 2014 — Pattern sequences: Luminous robots, ASYNC, non-rigid, chirality current best, Luminous robots, ASYNC, non-rigid, chirality lower bound
2015
Programmable matter · Self-organising particle systems
Leader election in programmable matter is posed in Derakhshandeh et al. 2015
Introduced with shape formation at DNA 21 (2015).
Programmable matter · Self-organising particle systems
Shape formation in programmable matter is posed in Derakhshandeh et al. 2015
Introduced with leader election at DNA 21 (2015).
- Erlebach et al. 2015 — Graph exploration by a single agent: Temporal graphs, schedule known current best, Temporal graphs, schedule known lower bound
- Czyzowicz et al. 2015 — Evacuation: Two face-to-face robots, disk lower bound
- Chrobak et al. 2015 — Evacuation: Line, any number of face-to-face robots current best, Line, any number of wireless robots current best, Line, any number of wireless robots lower bound
- Czyzowicz et al. 2015 — Evacuation: Triangle, two wireless robots starting on the boundary introduced
- Bouchard et al. 2015 — Gathering in graphs: Byzantine agents current best
- Bramas & Tixeuil 2015 — Scattering: Randomized, SSYNC, weak multiplicity detection current best, Randomized, SSYNC, weak multiplicity detection lower bound
- Vaidyanathan et al. 2015 — Mutual visibility: Lights, FSYNC, chirality current best
- Derakhshandeh et al. 2015 — Leader election in programmable matter: Randomized, with chirality introduced; Shape formation in programmable matter: SILBOT, full orientation lower bound
- Czyzowicz et al. 2015 — Patrolling: Graphs with faulty patrollers current best, Graphs with faulty patrollers lower bound
2016
Mobile agents on graphs · Exploration
Exploration of dynamic graphs by teams is posed in Di Luna et al. 2016
Live exploration of dynamic rings was posed at ICDCS 2016.
In the logical view: variant of Collaborative exploration, which was posed earlier (2004).
Programmable matter · Self-organising particle systems
Compression is posed in Cannon et al. 2016
PODC 2016.
- Disser et al. 2016 — Graph exploration by a single agent: Exploration with stop when \(n\) is known lower bound, Exploration with return and pebbles current best, Exploration with return and pebbles lower bound; Collaborative exploration: Anonymous graphs, a team of constant-memory agents current best, Anonymous graphs, a team of constant-memory agents lower bound
- Czyzowicz et al. 2016 — Linear search (cow path): \(k\) robots on a line, \(f\) crash faults current best
- Czyzowicz et al. 2016 — Linear search (cow path): \(k\) robots on a line, Byzantine faults current best
- Bampas et al. 2016 — Linear search (cow path): Two robots of different speeds, both must reach the target current best, Two robots of different speeds, both must reach the target lower bound; Evacuation: Line, any number of face-to-face robots lower bound, Line, two face-to-face robots of different speeds current best, Line, two face-to-face robots of different speeds lower bound, Line, two wireless robots of different speeds current best, Line, two wireless robots of different speeds lower bound
- Lamprou et al. 2016 — Evacuation: Disk, two wireless robots of different speeds current best, Disk, two wireless robots of different speeds lower bound
- Di Luna et al. 2016 — Exploration of dynamic graphs by teams: 1-interval-connected rings introduced, 1-interval-connected rings lower bound
- Derakhshandeh et al. 2016 — Shape formation in programmable matter: Universal shapes, sequential, randomized current best, Universal shapes, sequential, randomized lower bound
- Daymude et al. 2016 — Coating: Universal coating current best, Universal coating lower bound
- Cannon et al. 2016 — Compression: Markov chain, sequential current best
2017
Programmable matter · Self-organising particle systems
Bridging is posed in Arroyo et al. 2018
arXiv 2017; Natural Computing 2018.
In the logical view: generalisation of Compression, which was posed earlier (2016).
Programmable matter · Self-organising particle systems
Shape formation by hybrid programmable matter is posed in Gmyr et al. 2017
First presented at EuroCG 2017 (non-archival); DNA 24 (2018); Natural Computing 2020. The work began at a Dagstuhl seminar in 2016.
Programmable matter · Self-organising particle systems
Centralised transformations of modular robots is posed in Michail et al. 2019
arXiv 2017; JCSS 2019.
- Disser et al. 2017 — Collaborative exploration: Trees, complete communication lower bound, Trees with \(k = n\) agents current best, Trees with \(k = n\) agents lower bound; Dispersion: Trees lower bound, Rooted trees lower bound
- Pattanayak et al. 2017 — Gathering: Crash faults, SSYNC current best, Crash faults, SSYNC lower bound
- Poudel & Sharma 2017 — Gathering: Limited visibility, one common axis, ASYNC current best, Limited visibility, one common axis, ASYNC lower bound
- Heriban et al. 2017 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid current best
- Mondal & Chaudhuri 2017 — Uniform circle formation: Transparent fat robots, SSYNC current best
- Czyzowicz et al. 2017 — Evacuation: Three wireless robots, one crash fault current best, Three wireless robots, one crash fault lower bound, Three wireless robots, one Byzantine current best, Three wireless robots, one Byzantine lower bound
- Georgiou et al. 2017 — Evacuation: Disk, search-and-fetch, two wireless robots current best, Disk, search-and-fetch, two face-to-face robots current best, Disk, search-and-fetch, two face-to-face robots lower bound
- Brandt et al. 2017 — Evacuation: \(m\) rays, \(k = m\) wireless robots at the junction current best, \(m\) rays, \(k = m\) wireless robots at the junction lower bound
- Di Luna et al. 2017 — Mutual visibility: Lights, SSYNC, rigid current best, Lights, SSYNC, rigid lower bound, Lights, SSYNC, non-rigid current best, Lights, SSYNC, non-rigid lower bound, Lights, ASYNC, rigid introduced, Lights, ASYNC, rigid lower bound, Lights, ASYNC, non-rigid, one axis current best, Lights, ASYNC, non-rigid, one axis lower bound
- Sharma et al. 2017 — Mutual visibility: Lights, ASYNC, rigid current best, Lights, ASYNC, rigid lower bound
- Aljohani & Sharma 2017 — Mutual visibility: Lights, one crash, SSYNC, rigid, compass current best, Lights, one Byzantine robot lower bound
- Daymude et al. 2017 — Leader election in programmable matter: Randomized, with chirality current best
- Di Luna et al. 2017 — Shape formation in programmable matter: Deterministic, simply connected start, no chirality current best, Deterministic, simply connected start, no chirality lower bound
- Derakhshandeh et al. 2017 — Coating: Universal coating introduced, Universal coating lower bound
- Menc et al. 2017 — Exploration of recolourable graphs: Rotor-router: a pointer in every node lower bound
- Gmyr et al. 2017 — Shape formation by hybrid programmable matter: Planar current best, Planar lower bound
2018
Mobile agents on graphs · Exploration
Dispersion is posed in Augustine & Moses Jr. 2018
Posed at ICDCN 2018, fourteen years after collaborative exploration; the introductory paper already relates dispersion to \(n\)-robot collaborative exploration and takes its tree lower bound from it.
In the logical view: derived from Collaborative exploration, which was posed earlier (2004).
Programmable matter · Self-organising particle systems
Convex hull formation is posed in Daymude et al. 2020
arXiv 2018; ICDCN 2020.
Mobile agents on graphs · Exploration
Exploration by luminous robots is posed in Ooshita & Tixeuil 2018
Ring exploration by myopic robots with a two-colour light (SSS 2018).
In the logical view: variant of Exploration by oblivious robots, which was posed earlier (2007).
Programmable matter · Self-organising particle systems
Separation of coloured particles is posed in Cannon et al. 2019
arXiv 2018; APPROX/RANDOM 2019.
In the logical view: generalisation of Compression, which was posed earlier (2016).
- Augustine & Moses Jr. 2018 — Collaborative exploration: Anonymous graphs with \(k = n\) agents introduced; Dispersion: Arbitrary graph, arbitrary initial configuration introduced, Arbitrary graph, arbitrary initial configuration lower bound, Rooted initial configuration introduced, Rooted initial configuration lower bound, Asynchronous agents lower bound, Rings and paths introduced, Rings and paths lower bound, Trees introduced, Trees lower bound, Rooted trees current best, Rooted trees lower bound, Crash faults lower bound, Weak Byzantine agents lower bound, Weak Byzantine agents on rings lower bound, Weak Byzantine agents on grids lower bound
- Agarwalla et al. 2018 — Dispersion: Dynamic rings current best
- Cicerone et al. 2018 — Pattern formation: ASYNC, no agreement on coordinates current best
- Okumura et al. 2018 — Gathering: Rendezvous, external light (FCOM), SSYNC lower bound
- Terai et al. 2018 — Gathering: Gathering, full lights, SSYNC, no multiplicity detection current best, Gathering, full lights, ASYNC, no multiplicity detection introduced, Gathering, external light (FCOM), SSYNC, rigid current best, Gathering, internal light (FSTA), SSYNC, non-rigid introduced, Gathering, external light, sequential scheduler current best, Gathering, external light, sequential scheduler lower bound
- Feletti et al. 2018 — Uniform circle formation: Opaque robots with lights, FSYNC introduced
- Kupavskii & Welzl 2018 — Linear search (cow path): \(k\) robots on a line, \(f\) crash faults lower bound, \(k\) robots on a line, Byzantine faults lower bound; Evacuation: Line, \(2f+1\) wireless robots, \(f\) crash faults lower bound
- Czyzowicz et al. 2018 — Evacuation: Priority evacuation (queen and servants), disk current best, Priority evacuation (queen and servants), disk lower bound
- Pattanayak et al. 2018 — Evacuation: Two robots, two exits, face-to-face current best, Two robots, two exits, face-to-face lower bound, Two robots, two exits, wireless current best, Two robots, two exits, wireless lower bound
- Czyzowicz et al. 2018 — Evacuation: Disk, priority evacuation, queen and one servant introduced, Disk, priority evacuation, queen and two servants current best, Disk, priority evacuation, queen and two servants lower bound
- Sharma et al. 2018 — Mutual visibility: Fat robots, FSYNC, rigid introduced
- Gastineau et al. 2018 — Leader election in programmable matter: Stationary, chirality, no holes current best
- Bazzi & Briones 2018 — Leader election in programmable matter: Stationary, chirality, weak scheduler current best
- Ooshita & Tixeuil 2018 — Exploration by luminous robots: Rings, FSYNC, perpetual, \(\varphi = 1\) current best, Rings, FSYNC, perpetual, \(\varphi = 1\) lower bound, Rings, FSYNC, terminating, \(\varphi = 1\) current best, Rings, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, ASYNC, perpetual, \(\varphi = 1\) current best, Rings, ASYNC, perpetual, \(\varphi = 1\) lower bound, Rings, ASYNC, terminating, \(\varphi = 1\) current best, Rings, ASYNC, terminating, \(\varphi = 1\) lower bound
- Arroyo et al. 2018 — Bridging: Markov chain, sequential current best
2019
Search in geometric domains · Search, evacuation and patrolling
Chauffeuring a crashed robot is posed in Pattanayak et al. 2019
ALGOSENSORS 2019.
In the logical view: variant of Evacuation, which was posed earlier (2014).
- Kshemkalyani & Ali 2019 — Collaborative exploration: Anonymous graphs with \(k = n\) agents lower bound; Dispersion: Arbitrary graph, arbitrary initial configuration lower bound, Rooted initial configuration lower bound, Asynchronous agents introduced, Asynchronous agents lower bound, Rings and paths lower bound, Anonymous agents with randomness lower bound, Crash faults lower bound, Weak Byzantine agents lower bound, Strong Byzantine agents lower bound
- Molla & Moses Jr. 2019 — Dispersion: More agents than nodes current best, More agents than nodes lower bound, Anonymous agents with randomness introduced, Anonymous agents with randomness lower bound
- Bose et al. 2019 — Pattern formation: Opaque robots with lights, ASYNC, one axis, rigid current best, Opaque robots with lights, ASYNC, compass, rigid current best, Opaque oblivious robots, ASYNC, compass lower bound
- Bose et al. 2019 — Pattern formation: Opaque fat robots with lights, ASYNC, one axis current best
- Disser & Schmitt 2019 — Evacuation: Two face-to-face robots, disk current best
- Gotoh et al. 2019 — Exploration of dynamic graphs by teams: Temporally connected graphs, arbitrary topology current best, Temporally connected graphs, arbitrary topology lower bound
- Emek et al. 2019 — Leader election in programmable matter: Deterministic, no orientation current best
- Nagahama et al. 2019 — Exploration by luminous robots: Rings, ASYNC, perpetual, \(\varphi \ge 2\) current best
- Pattanayak et al. 2019 — Chauffeuring a crashed robot: \(e\) exits current best, One exit current best, Two exits current best
- Cannon et al. 2019 — Separation of coloured particles: Markov chain, sequential current best
- Michail et al. 2019 — Centralised transformations of modular robots: Rotation only current best, Rotation and sliding current best, Rotation and sliding lower bound
2020s
2020
Programmable matter · Self-organising particle systems
Energy distribution is posed in Daymude et al. 2021
arXiv 2020; ICDCN 2021.
- Kshemkalyani et al. 2020 — Dispersion: Grids current best, Grids lower bound, Crash faults on grids lower bound, Weak Byzantine agents on grids lower bound
- Kshemkalyani et al. 2020 — Dispersion: Dynamic graphs (1-interval connected) lower bound, Dynamic graphs with global communication current best, Dynamic graphs with global communication lower bound
- Molla et al. 2020 — Dispersion: Weak Byzantine agents on rings current best, Weak Byzantine agents on rings lower bound
- Mondal et al. 2020 — Uniform circle formation: Opaque fat robots, ASYNC, limited visibility, compass current best
- Chuangpishit et al. 2020 — Evacuation: Two face-to-face robots, equilateral triangle current best, Two face-to-face robots, equilateral triangle lower bound, Two face-to-face robots, square current best, Two face-to-face robots, square lower bound, Triangle, any number of face-to-face robots current best, Triangle, any number of face-to-face robots lower bound
- D'Angelo et al. 2020 — Leader election in programmable matter: Silent oblivious particles (SILBOT) current best, SILBOT with holes current best, SILBOT with holes lower bound
- Daymude et al. 2020 — Convex hull formation: No orientation current best
- Kawamura & Soejima 2020 — Patrolling: Open fence, distinct speeds current best, Closed fence, distinct speeds current best
2021
Mobile robots in the plane · Formation problems
Partitioning is posed in Bhagat et al. 2021
The fixed-point version (\(k\)-EPF) was posed with \(k\)-circle formation in 2021; the earlier partitioning of Efrima and Peleg fixes the number of groups instead and is recorded under \(k\)-grouping.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
- Das et al. 2021 — Dispersion: Anonymous agents with randomness current best
- Pattanayak et al. 2021 — Dispersion: Crash faults introduced
- Molla et al. 2021 — Dispersion: Weak Byzantine agents current best, Weak Byzantine agents lower bound, Strong Byzantine agents introduced
- Bouchard et al. 2021 — Treasure hunt: Labelled nodes, locally finite graphs current best, Labelled nodes, locally finite graphs lower bound
- Gorain et al. 2021 — Treasure hunt: Treasure hunt guided by pebbles current best, Treasure hunt guided by pebbles lower bound
- Nakai et al. 2021 — Gathering: Gathering, full lights, ASYNC, no multiplicity detection current best
- Kirkpatrick et al. 2021 — Convergence: Limited visibility, asynchronous current best
- Czyzowicz et al. 2021 — Evacuation: Line, a sender and a receiver current best, Line, a sender and a receiver lower bound
- Czyzowicz et al. 2021 — Evacuation: Line, \(2f+1\) wireless robots, \(f\) crash faults current best
- Di Luna et al. 2021 — Black hole search: Dynamic rings current best, Dynamic rings lower bound
- Dufoulon et al. 2021 — Leader election in programmable matter: Deterministic, with chirality current best
- Bramas et al. 2021 — Exploration by luminous robots: Grids, FSYNC, perpetual, chirality, \(\varphi = 1\) current best, Grids, FSYNC, perpetual, chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, perpetual, chirality, \(\varphi = 2\) current best, Grids, FSYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) current best, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, FSYNC, terminating, chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, terminating, chirality, \(\varphi = 2\) lower bound, Grids, FSYNC, terminating, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, terminating, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, terminating, no chirality, \(\varphi = 2\) lower bound
- Rauch et al. 2021 — Exploration by luminous robots: Grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) current best, Grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 3\) lower bound
- Nagahama et al. 2021 — Exploration by luminous robots: Grids, FSYNC, terminating, chirality, \(\varphi = 1\) current best, Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) current best, Grids, FSYNC, terminating, chirality, \(\varphi = 2\) current best, Grids, FSYNC, terminating, no chirality, \(\varphi = 2\) current best, Grids, ASYNC, terminating, chirality, \(\varphi = 1\) current best, Grids, ASYNC, terminating, chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) current best, Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, terminating, chirality, \(\varphi = 2\) current best, Grids, ASYNC, terminating, no chirality, \(\varphi = 2\) current best
- Bhagat et al. 2021 — Partitioning: Exactly \(n/k\) robots at each fixed point current best
- Daymude et al. 2021 — Energy distribution: Unfair adversary current best, Unfair adversary lower bound
2022
Programmable matter · Self-organising particle systems
Alignment is posed in Kedia et al. 2022
APPROX/RANDOM 2022.
In the logical view: generalisation of Compression, which was posed earlier (2016).
- Kshemkalyani et al. 2022 — Dispersion: Global communication introduced, Global communication lower bound
- Italiano et al. 2022 — Dispersion: Directed graphs current best, Directed graphs lower bound, Directed graphs, 1-hop communication current best, Directed graphs, 1-hop communication lower bound
- Gorain et al. 2022 — Dispersion: Silent agents (no communication) current best, Silent agents (no communication) lower bound, Silent agents on rings lower bound
- Castenow et al. 2022 — Gathering: Limited visibility, FSYNC, disoriented current best, Limited visibility, FSYNC, disoriented lower bound; Near-gathering: SSYNC, limited visibility, disoriented current best, SSYNC, limited visibility, disoriented lower bound
- Feletti et al. 2022 — Uniform circle formation: Opaque robots with lights, ASYNC introduced, Opaque robots with lights, FSYNC current best
- Georgiou et al. 2022 — Evacuation: Two robots with asymmetric communication, disk current best, Two robots with asymmetric communication, disk lower bound
- Georgiou & Jang 2022 — Evacuation: Triangle, two wireless robots starting on the boundary current best, Triangle, two wireless robots starting on the boundary lower bound
- Alsaedi et al. 2022 — Mutual visibility: Fat robots, FSYNC, rigid current best, Fat robots, FSYNC, rigid lower bound
- Darwich et al. 2022 — Exploration by luminous robots: Tori, FSYNC, perpetual, chirality, \(\varphi = 1\) current best, Tori, FSYNC, perpetual, chirality, \(\varphi = 1\) lower bound, Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) current best, Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) lower bound, Tori, FSYNC, perpetual, chirality, \(\varphi = 2\) current best, Tori, FSYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) current best, Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) lower bound
- Bojko et al. 2022 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph lower bound, Recolourable nodes on cacti lower bound, Recolourable nodes on trees lower bound, Label-guided: colours fixed by a designer lower bound
- Kedia et al. 2022 — Alignment: Markov chain, sequential current best
2023
Mobile agents on graphs · Computing with agents
Minimal dominating set by agents is posed in Chand et al. 2023
Introduced at ALGOSENSORS 2023.
Mobile robots in the plane · Symmetry breaking and spreading
Separation is posed in Seike & Yamauchi 2023
Introduced at SSS 2023.
Mobile agents on graphs · Exploration
Exploration of recolourable graphs is posed in Böckenhauer et al. 2023
Böckenhauer, Frei, Unger and Wehner posed exploration by an oblivious agent without port numbers that colours nodes and sees its neighbours' colours (SIROCCO 2023; arXiv January 2023), first with each node coloured once and, in a last section, with recolouring. Fixed colours chosen by a designer (2005) and the rotor-router pointer (1996, 2003) are earlier node-side precursors.
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
Programmable matter · Self-organising particle systems
Scattering of particles is posed in Navarra et al. 2025
Scattering in SILBOT first appeared at AINA 2023 (Navarra, Prencipe, Bonini, Tracolli); that paper's DOI was not verified, so the journal version is cited.
- Cosson et al. 2023 — Collaborative exploration: Trees, asynchronous, complete communication introduced, Arbitrary graphs, complete communication current best
- Pattanayak et al. 2023 — Dispersion: Crash faults current best
- Pattanayak & Pelc 2023 — Treasure hunt: Anonymous graphs with possibly infinite degrees current best, Anonymous graphs with possibly infinite degrees lower bound; Rendezvous: Labelled agents, graphs with infinite degrees current best, Labelled agents, graphs with infinite degrees lower bound
- Alsaedi et al. 2023 — Pattern formation: Fat robots with lights, FSYNC, randomized, no agreement current best
- Asahiro & Yamashita 2023 — Gathering: Homonymous robots, SSYNC current best, Homonymous robots, SSYNC lower bound
- Bramas et al. 2023 — Gathering: Rendezvous, full lights, a crash, SSYNC lower bound
- Molla et al. 2023 — Gathering in graphs: Labelled agents current best
- Chand et al. 2023 — Minimal dominating set by agents: No knowledge introduced
- Seike & Yamauchi 2023 — Separation: ASYNC, one common axis introduced
- Briones et al. 2023 — Leader election in programmable matter: Stationary, asynchronous, no orientation, no holes current best, Stationary, sequential, no orientation, no holes current best
- Navarra & Piselli 2023 — Shape formation in programmable matter: SILBOT, chirality lower bound, SILBOT, full orientation current best
- Navarra & Piselli 2023 — Coating: SILBOT, chirality, deterministic current best, SILBOT, chirality, deterministic lower bound
- Böckenhauer et al. 2023 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph introduced, Once-colourable nodes, any graph current best, Once-colourable nodes, any graph lower bound, Once-colourable nodes, \(n\) known current best, Once-colourable nodes, \(n\) known lower bound, Once-colourable nodes on trees current best, Once-colourable nodes on trees lower bound
2024
Mobile agents on graphs · Computing with agents
Leader election by agents is posed in Kshemkalyani et al. 2024
Leader election in the agent-based model, with MST as an application (DISC 2024).
Mobile agents on graphs · Computing with agents
Maximal independent set by agents is posed in Pattanayak et al. 2024
Introduced at ICDCN 2024.
Mobile agents on graphs · Computing with agents
Triangle and butterfly counting by agents is posed in Chand et al. 2026
Agent-based triangle counting (arXiv 2024; IEEE Transactions on Networking 2026).
Mobile agents on graphs · Computing with agents
Minimum spanning tree by agents is posed in Kshemkalyani et al. 2024
MST in the agent-based model appeared together with leader election (DISC 2024).
- Pattanayak & Pelc 2024 — Graph exploration by a single agent: Memoryless automaton with pebbles current best, Memoryless automaton with pebbles lower bound
- Banerjee et al. 2024 — Dispersion: Crash faults on grids introduced
- Moses Jr. & Redlich 2024 — Dispersion: Strong Byzantine agents current best
- Hahn et al. 2024 — Pattern formation: Limited visibility current best
- Otaka et al. 2024 — Gathering: Rendezvous, external light (FCOM), SSYNC lower bound, Rendezvous, external light (FCOM), ASYNC, non-rigid lower bound, Rendezvous, external light (FCOM), ASYNC, rigid lower bound, Rendezvous, internal light (FSTA), SSYNC, non-rigid lower bound, Rendezvous, internal light (FSTA), SSYNC, rigid lower bound, Rendezvous, internal light (FSTA), ASYNC lower bound, Gathering, external light (FCOM), SSYNC, rigid lower bound, Gathering, internal light (FSTA), SSYNC, non-rigid current best, Gathering, internal light (FSTA), SSYNC, non-rigid lower bound
- Feletti et al. 2024 — Uniform circle formation: Opaque robots with lights, ASYNC current best, Opaque robots with lights, ASYNC lower bound
- Georgiou & Wang 2024 — Evacuation: Disk, priority evacuation, queen and one servant current best, Disk, priority evacuation, queen and one servant lower bound
- Kshemkalyani et al. 2024 — Leader election by agents: No knowledge introduced; Maximal independent set by agents: No knowledge introduced; Minimum spanning tree by agents: Dispersed start introduced
- Pattanayak et al. 2024 — Maximal independent set by agents: Knowing \(n\) and \(\Delta\) introduced
- Bhagat et al. 2024 — Mutual visibility: Fat robots, ASYNC, one axis current best
- Flocchini et al. 2024 — Separation: ASYNC, one common axis current best, ASYNC, one common axis lower bound
- Chalopin et al. 2024 — Leader election in programmable matter: Stationary, common direction, no chirality current best, Stationary, common direction, no chirality lower bound
- Ooshita et al. 2024 — Exploration by luminous robots: Rings, ASYNC, perpetual, \(\varphi \ge 2\) lower bound, Rings, FSYNC, perpetual, up to \(f\) crashes current best, Rings, FSYNC, perpetual, up to \(f\) crashes lower bound, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi = 1\) current best, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi = 1\) lower bound, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi \ge 2\) current best, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi \ge 2\) lower bound
- Bramas et al. 2024 — Exploration by luminous robots: Grids, ASYNC, perpetual, chirality, \(\varphi = 1\) (exclusive) lower bound, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) current best, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 3\) current best
- Hinnenthal et al. 2024 — Shape formation by hybrid programmable matter: Three-dimensional current best
2025
Mobile robots in the plane · Formation problems
Universal pattern formation is posed in Flocchini et al. 2025
Introduced at SIROCCO 2025.
In the logical view: strengthening of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Computing with agents
BFS tree by agents is posed in Chand et al. 2025
BFS without root knowledge in the agent-based model (SSS 2025).
- Cosson & Massoulié 2025 — Collaborative exploration: Trees, asynchronous, complete communication lower bound, Trees, asynchronous, whiteboards only current best
- Kshemkalyani et al. 2025 — Collaborative exploration: Anonymous graphs with \(k = n\) agents current best; Dispersion: Arbitrary graph, arbitrary initial configuration current best, Rooted initial configuration current best, Global communication current best, Rings and paths current best, Trees current best
- Pattanayak et al. 2025 — Dispersion: Asynchronous agents current best
- Mondal et al. 2025 — Dispersion: Dynamic rings lower bound
- Banerjee et al. 2025 — Dispersion: Crash faults on grids current best, Weak Byzantine agents on grids current best
- Das et al. 2025 — Dispersion: Silent agents (no communication) lower bound, Silent agents on rings current best, Silent agents on rings lower bound
- Di Luna et al. 2025 — Black hole search: Byzantine companions, with a map current best, Byzantine companions, whiteboards, no map current best
- Flocchini et al. 2025 — Universal pattern formation: Sequential schedulers current best, Sequential schedulers lower bound
- Chand et al. 2025 — Triangle and butterfly counting by agents: Butterfly counting in bipartite graphs current best
- Chand et al. 2025 — Minimum spanning tree by agents: Dispersed start current best; BFS tree by agents: Dispersed start, root unknown current best
- Chalopin et al. 2025 — Leader election in programmable matter: Stationary, fair scheduler, no orientation, no holes current best
- Takahashi et al. 2025 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph current best
- Navarra et al. 2025 — Scattering of particles: SILBOT current best
2026
- Cosson & Massoulié 2026 — Collaborative exploration: Trees, complete communication current best, Trees, asynchronous, complete communication current best
- Masuzawa et al. 2026 — Gathering: Rendezvous, external light (FCOM), ASYNC, rigid current best, Rendezvous, internal light (FSTA), SSYNC, rigid current best
- Devismes et al. 2026 — Gathering in graphs: Homonymous agents current best
- Chand & Molla 2026 — Leader election by agents: No knowledge current best; Minimal dominating set by agents: No knowledge current best
- Kshemkalyani et al. 2026 — Leader election by agents: Knowing \(n\) and \(\Delta\) current best; Maximal independent set by agents: Knowing \(n\) and \(\Delta\) current best
- Kaur et al. 2026 — Maximal independent set by agents: No knowledge current best
- Feletti et al. 2026 — Pattern sequences: Luminous robots, sequential scheduler (universal dancing) current best, Luminous robots, sequential scheduler (universal dancing) lower bound
- Pyati et al. 2026 — Separation: Opaque robots, SSYNC current best
- Chand et al. 2026 — Triangle and butterfly counting by agents: Triangle counting current best
- Chalopin et al. 2026 — Leader election in programmable matter: Oblivious, common compass, holes allowed current best
- Hiraoka et al. 2026 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph lower bound, Recolourable nodes on cacti current best, Recolourable nodes on cacti lower bound, Recolourable nodes on trees current best, Recolourable nodes on trees lower bound