Author name cluster

Gabriele Di Stefano

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

1 author row

TCS Journal 2026 Journal Article

On the approximability of graph visibility problems

Davide Bilò
Alessia Di Fonso
Gabriele Di Stefano
Stefano Leucci

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.

Details DOI

TCS Journal 2025 Journal Article

Optimal gathering of robots in anonymous butterfly networks via leader election

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

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.

Details DOI

TCS Journal 2024 Journal Article

Molecular pattern formation on grids in the Moblot model

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

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.

Details DOI

TCS Journal 2023 Journal Article

Arbitrary pattern formation on infinite regular tessellation graphs

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

Given a set R of robots, each one located at a different vertex of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that | R | = | F |, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical OBLOT model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. In particular, the former can be considered as the most general in terms of possible symmetries and trajectories. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph. The algorithm and its correctness are based on a rigorous methodology.

Details DOI

TCS Journal 2023 Journal Article

Variety of mutual-visibility problems in graphs

Serafino Cicerone
Gabriele Di Stefano
Lara Drožđek
Jaka Hedžet
Sandi Klavžar
Ismael G. Yero

If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u, v -path P such that V ( P ) ∩ X ⊆ { u, v }. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.

Details DOI

TCS Journal 2022 Journal Article

A graph theoretical approach to the firebreak locating problem

Marc Demange
Alessia Di Fonso
Gabriele Di Stefano
Pierpaolo Vittorini

In the last decade, wildfires have become wider and more destructive. Climate change and the growth of urban areas are among the main factors that increase the risk of large-scale fires. This risk can be lowered with preventive measures. Among them, firefighting lines are used to stop the fire spread and to offer a safe corridor where firefighting resources can be deployed. Due to their high cost of installation and maintenance, the placement of these lines must be carefully planned. In this work, we address this problem from a theoretical perspective. The land is modeled by a mixed graph in which vertices represent areas subject to burn while edges model the possibility of fire spreading from one area to another. Vertices are associated with probabilities of ignition and edges with probabilities of spread. We consider the problem of positioning firefighting lines such that the risk is reduced under a budget constraint. We call this problem Firebreak Location. We study its complexity and prove in particular its NP-hardness even when the graph is planar, bipartite, with a maximum degree four and the probabilities of propagation are equal to one. Planarity and low degree are indeed natural properties of real instances. We also show an efficient polynomial time algorithm for particular instances on trees.

Details DOI

TCS Journal 2021 Journal Article

Gathering robots in graphs: The central role of synchronicity

Serafino Cicerone
Gabriele Di Stefano
Alfredo Navarra

The Gathering task for k robots disposed on the n vertices of a graph G requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting and innovative sufficient condition for the feasibility of the gathering task in graphs, regardless the topology. Furthermore, we consider dense and symmetric graphs like complete and complete bipartite graphs where in general the topology does not allow to distinguish vertices where to finalize the gathering. In such topologies, we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising from the general approach with specific techniques dictated by the considered topologies. From the lower bound point of view in terms of number of synchronous time units required to accomplish the gathering task, in general nothing better than Ω ( D G ), with D G being the diameter of the input graph G, can be provided. For both complete and complete bipartite graphs, we prove a lower bound of Ω ( log ϕ ⁡ k ), with ϕ being the well-known golden ratio. Combined with the provided algorithms, this reveals to be asymptotically tight for complete graphs while for complete bipartite graphs an additive factor of δ ( k ) is achieved, with δ ( k ) being the function that returns the number of divisors of the integer k.

Details DOI

AAMAS Conference 2021 Conference Paper

MOBLOT: Molecular Oblivious Robots

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

In swarm robotics, research mainly follows a theoretical approach that considers robot systems in the abstract, where the complexity and capabilities of the underlying model are often reduced to their minimum. One general and well-investigated model is OBLOT, where the robots are silent, anonymous, and oblivious. In this work, we introduce MOBLOT, a model that extends OBLOT to address a larger spectrum of cases. MOBLOT stands for molecular oblivious robots: like atoms combine themselves to form molecules, in MOBLOT simple robots can move to form more complex computational units, having an extent and different capabilities with respect to robots; like molecules combine themselves to form the matter, in MOBLOT the complex structures can exploit their own capabilities to arrange themselves to form any shape defining an acceptable final structure. In MOBLOT, we formally define the Matter Formation (MF) problem and, as a preliminary general result, we provide a necessary condition for its solvability which relies on symmetricity. Informally, the symmetricity of a configuration measures the amount of symmetries of the robots’ disposal. We actually show how dealing with molecules can resolve in some cases the symmetry breaking issue where OBLOT cannot. Finally, we provide a case study for MOBLOT, that is, a representative MF problem along with a resolution distributed algorithm.

PDF

TCS Journal 2019 Journal Article

Approximation algorithms for decomposing octilinear polygons

Serafino Cicerone
Gabriele Di Stefano

We study the minimal decomposition of octilinear polygons with holes into octilinear triangles and rectangles. This new problem is relevant in the context of modern electronic CAD systems, where the generation and propagation of electromagnetic noise into multi-layer PCBs has to be detected. It is a generalization of a problem deeply investigated: the minimal decomposition of rectilinear polygons into rectangles. We show that the new problem is NP-hard. We also show the NP-hardness of a related problem, that is the decomposition of an octilinear polygon with holes into octilinear convex polygons. For both problems, we propose efficient approximation algorithms.

Details DOI

I&C Journal 2018 Journal Article

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane

Mattia D'Emidio
Gabriele Di Stefano
Daniele Frigioni
Alfredo Navarra

In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi-synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i. e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.

Details DOI

I&C Journal 2017 Journal Article

Gathering of oblivious robots on infinite grids with minimum traveled distance

Gabriele Di Stefano
Alfredo Navarra

A largely studied version of the gathering problem asks to move a set of robots initially placed at different vertices of an anonymous graph toward a common vertex, and to let them remain at such a vertex. Asynchronous robots move based on the so-called Look–Compute–Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move toward one of its neighbors (Compute), and then it performs the computed move (Move), eventually. So far, the main goal has been to detect the minimal assumptions that allow to accomplish the task, without taking care of any cost measure. In this paper, we are interested in optimal algorithms in terms of total number of moves. We consider infinite grids, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.

Details DOI

TCS Journal 2016 Journal Article

Gathering of robots on anonymous grids and trees without multiplicity detection

Gianlorenzo D'Angelo
Gabriele Di Stefano
Ralf Klasing
Alfredo Navarra

The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look–Compute–Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case.

Details DOI

TCS Journal 2010 Journal Article

Partially dynamic efficient algorithms for distributed shortest paths

Serafino Cicerone
Gianlorenzo D’Angelo
Gabriele Di Stefano
Daniele Frigioni

We study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite) due to the looping and counting infinity phenomena. In this paper, we propose partially dynamic algorithms that are able to concurrently update shortest paths. We experimentally analyze the effectiveness and efficiency of our algorithms by comparing them against several implementations of the well-known Bellman–Ford algorithm.

Details DOI

TCS Journal 2003 Journal Article

A fully dynamic algorithm for distributed shortest paths

Serafino Cicerone
Gabriele Di Stefano
Daniele Frigioni
Umberto Nanni

We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If Δ σ is the number of pairs of nodes changing the distance after a single edge modification σ (insert, delete, weight decrease, or weight increase) then the message complexity of the proposed algorithm is O(nΔ σ ) in the worst case, where n is the number of nodes of the network. If Δσ = o(n2), this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.

Details DOI

TCS Journal 2002 Journal Article

Static and dynamic low-congested interval routing schemes

Serafino Cicerone
Gabriele Di Stefano
Michele Flammini

Interval routing schemes (IRS) have been extensively investigated in the past years with special emphasis on shortest paths. Besides their theoretical interest, IRS have practical applications, as they have been implemented with wormhole routing in the last generation of INMOS transputer router chips. In this paper we consider IRS that are optimal with respect to the congestion of the induced path system. In fact, wormhole routing is strongly influenced by the maximum number of paths that share a physical link and from low to moderate congestion it outperforms the packet switching technique. We provide a general framework able to deal with the various congestion issues in IRS. In fact, we will distinguish between static cases, in which the source–destination configurations are fixed, and dynamic cases, where they vary over time. All these situations can be handled in a unified setting, thanks to the notion of competitiveness introduced in this paper. We first give some general results not related to specific traffic demands. Then, in the one-to-all communication pattern, we show that constructing competitive IRS for a given network is an intractable problem, both for the static and the dynamic case, that is when the root vertex is fixed and when it can change along the time, respectively. Finally, both for one-to-all and all-to-all communication patterns, we provide nicely competitive k-IRS for relevant topologies. Networks considered are chains, trees, rings, chordal rings and multi-dimensional grids and tori. We consider both the directed congestion case, in which there are pairwise opposite unidirectional links connecting two neighbor processors, and the undirected congestion case, in which two neighbors are connected by a single bi-directional link.

Details DOI