Search

Two Dots is a popular single-player puzzle video game for iOS and Android. A level of this game consists of a grid of colored dots. The player connects two or more adjacent dots, removing them from the grid and causing the remaining dots to fall, as if influenced by gravity. One special move, which is frequently a game-changer, consists of connecting a cycle of dots: this removes all the dots of the given color from the grid. The goal is to remove a certain number of dots of each color using a limited number of moves. The computational complexity of Two Dots has already been addressed in [Misra, FUN 2016], where it has been shown that the general version of the problem is NP-complete. Unfortunately, the known reductions produce Two Dots levels having both a large number of colors and many columns. This does not completely match the spirit of the game, where, on the one hand, only few colors are allowed, and on the other hand, the grid of the game has only a constant number of columns. In this paper, we partially fill this gap by assessing the computational complexity of Two Dots instances having a small number of colors or columns. More precisely, we show that Two Dots is hard even for instances involving only 3 colors or 2 columns. As a contrast, we also prove that the problem can be solved in polynomial-time on single-column instances with a constant number of goals., Leibniz International Proceedings in Informatics (LIPIcs), 100, ISSN:1868-8969, 9th International Conference on Fun with Algorithms (FUN 2018), ISBN:978-3-95977-067-5

We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n^2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time., Leibniz International Proceedings in Informatics (LIPIcs), 92, ISSN:1868-8969, 28th International Symposium on Algorithms and Computation (ISAAC 2017), ISBN:978-3-95977-054-5

Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algorithmic flavour which are related with this game, namely Solitaire-Reachability and Solitaire-Army. In the first one, we show that deciding whether there is a sequence of jumps which allows a given initial configuration of pegs to reach a target position is NP-complete. Regarding Solitaire-Army, the aim is to successfully deploy an army of pegs in a given region of the board in order to reach a target position. By solving an auxiliary problem with relaxed constraints, we are able to answer some open questions raised by Cs\'ak\'any and Juh\'asz (Mathematics Magazine, 2000). To appreciate the combinatorial beauty of our solutions, we recommend to visit the gallery of animations provided at http://solitairearmy.isnphard.com., Comment: Conference version

Given an n-vertex and m-edge non-negatively real-weighted graph G = (V,E,w), whose vertices are partitioned into a set of k clusters, a clustered network design problem on G consists of finding a (possibly optimal) solution to a given network design problem on G, subject to some additional constraint on its clusters. In this paper, we focus on the classic shortest-path tree problem and summarize our ongoing work in this field. In particular, we analyze the hardness of a clustered version of the problem in which the additional feasibility constraint consists of forcing each cluster to form a (connected) subtree.