Author name cluster

Stefano Leucci

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.

10 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

Uniform-budget solo chess with only rooks or only knights is hard

Davide Bilò
Luca Di Donato
Luciano Gualà
Stefano Leucci

We study the Solo-Chess problem which has been introduced in [Aravind et al. , FUN 2022]. This is a single-player variant of chess in which the player must clear all but one piece from the board via a sequence captures while ensuring that each piece performs at most as many captures as its budget allows. The time complexity of finding a winning sequence of captures has already been pinpointed for several combinations of piece types and initial budgets. We contribute to a better understanding of the computational landscape of Solo-Chess by closing two problems left open in [Aravind et al. , FUN 2022]. Namely, we show that Solo-Chess is hard even when all pieces are restricted to only rooks with budget exactly 2, or only knights with budget exactly 11.

Details DOI

TCS Journal 2022 Journal Article

Cutting bamboo down to size

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti
Giacomo Scornavacca

This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al. , SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i. e. , the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i. e. , the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O ( log ⁡ n ) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to 3 + 5 2 < 2. 62 for x = 1 + 1 5. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).

Details DOI

TCS Journal 2022 Journal Article

New approximation algorithms for the heterogeneous weighted delivery problem

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti
Mirko Rossi

We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al. , STACS'17] where k heterogeneous mobile agents (e. g. , robots, vehicles, etc.), initially positioned on vertices of an n-vertex edge-weighted graph G, have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1, and is 4ρ-approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O ( log ⁡ n ), closing a problem left open in [Bärtschi et al. , ATMOS'17]. This algorithm can be turned into an O ( k ) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ ( log 3 ⁡ n ) -approximation algorithm for the general case.

Details DOI

TCS Journal 2020 Journal Article

Tracking routes in communication networks

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti

The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph G and a set of source-destination pairs of vertices is a subset T of vertices of G such that the vertices in T traversed by any source-destination shortest path P uniquely identify P. The minimum tracking set problem has been introduced in Banik et al. , CIAC (2017) [1] for the case of a single source-destination pair. There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case. In this paper we focus on the case of multiple source-destination pairs and we present the first O ˜ ( n ) -approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs S × D, where S and D are the sets of sources and destinations, respectively. Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w. r. t. the maximum number of vertices at the same distance from the source.

Details DOI

TCS Journal 2020 Journal Article

Tracks from hell — When finding a proof may be easier than checking it

Matteo Almanza
Stefano Leucci
Alessandro Panconesi

We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al. , FUN 2016] that the problem of finding a solution to a given Trainyard instance (i. e. , game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i. e. , a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.

Details DOI

TCS Journal 2018 Journal Article

Trainyard is NP-Hard

Matteo Almanza
Stefano Leucci
Alessandro Panconesi

Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that these features are somehow related to their computational complexity [6]. Indeed, many puzzle games – such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few – are known to be NP-hard [3, 4, 8, 12]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also provide an implementation of our hardness reduction.

Details DOI

TCS Journal 2016 Journal Article

Exact and approximate algorithms for movement problems on (special classes of) graphs

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti

When a large collection of objects (e. g. , robots, sensors, etc.) has to be deployed in a given environment, it is often required to plan a coordinated motion of the objects from their initial position to a final configuration enjoying some global property. In such a scenario, the problem of minimizing some function of the distance travelled, and therefore of reducing energy consumption, is of vital importance. In this paper we study several motion planning problems that arise when the objects initially sit on the vertices of a graph, and they must be moved so as that the final vertices that receive (at least) one object induce a subgraph enjoying a given property. In particular, we consider the notable properties of connectivity, independence, completeness, and finally that of being a vertex-cutset w. r. t. a pair of fixed vertices. We study these problems with the aim of minimizing a number of natural measures, namely the average/overall distance travelled, the maximum distance travelled, and the number of objects that need to be moved. To this respect, we provide several approximability and inapproximability results, most of which are tight.

Details DOI

TCS Journal 2015 Journal Article

Specializations and generalizations of the Stackelberg minimum spanning tree game

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti

Let be given a graph G = ( V, E ) whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and form a spanning tree of G. Then, the Stackelberg Minimum Spanning Tree (StackMST) problem is that of pricing (i. e. , weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. StackMST is known to be APX-hard already when the number of distinct red edge weights is 2. In this paper we analyze some meaningful specializations and generalizations of StackMST, which shed some more light on the computational complexity of the problem. More precisely, we first show that if G is restricted to be complete, then the following holds: (i) if there are only 2 distinct red edge weights, then the problem can be solved optimally (this contrasts with the corresponding APX-hardness of the general problem); (ii) otherwise, the problem can be approximated within 7 / 4 + ϵ, for any ϵ > 0. Afterwards, we define a natural extension of StackMST, namely that in which blue edges are associated with a non-negative activation cost, and it is given a global activation budget that can be used (and must not be exceeded) in order to activate a subset of blue edges to be priced. Here, after showing that the very same approximation ratio as that of the original problem can be achieved, we prove that if the spanning tree of red edges can be rooted so as that any root-leaf path contains at most h edges, then the problem admits a ( 2 h + ϵ ) -approximation algorithm, for any ϵ > 0.

Details DOI

TCS Journal 2015 Journal Article

The max-distance network creation game on general host graphs

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti

In this paper we study a generalization of the classic network creation game in the scenario in which the n players sit on a given arbitrary host graph, which constrains the set of edges a player can activate at a cost of α ≥ 0 each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player her maximum distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for very simple host graph topologies. More precisely, we first exhibit a lower bound of Ω ( n / ( 1 + α ) ) for any α = o ( n ). Notice that this implies a counter-intuitive lower bound of Ω ( n ) even for α = 0, i. e. , when edges can be activated for free. Then, we show that when the host graph is restricted to be either k-regular (for any constant k ≥ 3 ), or a 2-dimensional grid, the PoA is still Ω ( 1 + min ⁡ { α, n α } ), which is proven to be tight for α = Ω ( n ). On the positive side, if α ≥ n, we show that the PoA is at most 2. Finally, in the case in which the host graph is very sparse (i. e. , | E ( H ) | = n − 1 + k, with k = O ( 1 ) ), we prove that the PoA is O ( 1 ), for any α.

Details DOI