The severity of wildfires can be mitigated using preventive measures like the construction of firebreaks, which are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location . A land of unknown size is modeled as an infinite undirected graph in which the vertices correspond to areas subject to fire and edges represent fire propagation from one area to another. A firebreak construction is modeled as removing the edge between two vertices. The number of firebreaks that can be installed depends on budget constraints. We assume that a fire ignites in a subset of vertices and propagates to the neighbors. The goal is to select a subset of edges to remove in order to contain the fire and avoid burning an infinite part of the graph. We prove that Infinite Windy Firebreak Location is coNP-complete in restricted cases, and we address some polynomial cases. We show that Infinite Windy Firebreak Location polynomially reduces to Min Cut for certain classes of graphs like infinite grid graphs and polyomino-grids.

Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph G of n vertices asks to find the largest set of vertices X ⊆ V ( G ), also called μ -set, such that for any two vertices u, v ∈ X , there is a shortest u, v -path P where all internal vertices of P are not in X . This means that u and v are visible w.r.t. X . Variations of this problem are known as total, outer , and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside X . The mutual-visibility problem and all its variants are known to be NP -complete on graphs of diameter 4. We design a polynomial-time algorithm that finds a μ -set of size Ω ( n / D ) , where D is the average distance in G , we show inapproximability results for all visibility problems on graphs of diameter 2, and we strengthen the inapproximability ratios for graphs of diameter 3 or larger. More precisely, assuming P ≠ NP , the mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n 1 / 3 − ε on graphs of diameter at least 3, while the outer and total mutual-visibility problems are not approximable within a factor of n 1 / 2 − ε , for any constant ε > 0. Finally, we study the relationship between the mutual-visibility number and the general position number, in which no three distinct vertices u, v, w of X belong to any shortest path of G .

Robots with very weak capabilities placed on the vertices of a graph are required to move toward a common vertex from where they do not move anymore. The task is known as the Gathering problem and it has been extensively studied in the last decade with respect to both general graphs and specific topologies. Most of the challenges faced are due to possible isometries observable from the placement of the robots with respect to the underlying topology. Rings, Grids, and Complete graphs are just a few examples of very regular topologies where the placement of the robots and suitable movements are crucial for succeeding in Gathering. Here we are interested in understanding what can be done in Butterfly graphs where really many isometries are present and most importantly unavoidable by any movement. We propose a Gathering algorithm for the so-called leader configurations, i.e., those where the initial placement of the robots admits the detection (and election) of one robot as the leader. We introduce a non-trivial technique to elect the leader which is of its own interest. We also prove that the proposed Gathering algorithm is asymptotically optimal in terms of synchronous rounds required.

In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the Moblot model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified.

The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the Geodesic Mutual Visibility (GMV) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of trees and (finite or infinite) square grids, for robots operating under the standard Look-Compute-Move model. In both scenarios, we provide resolution algorithms along with formal correctness proofs, highlighting the most relevant peculiarities arising within the different contexts, while optimizing the time complexity.