DROPS

Volume

LIPIcs, Volume 366

13th International Conference on Fun with Algorithms (FUN 2026)

FUN 2026, Porquerolles, France, May 18-22, 2026

Editors: John Iacono

Volume

LIPIcs, Volume 308

32nd Annual European Symposium on Algorithms (ESA 2024)

ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom

Editors: Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman

Document

Front Matter

DOI: 10.4230/LIPIcs.FUN.2026.0

Front Matter, Table of Contents, Preface, Conference Organization

Authors: John Iacono

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Front Matter, Table of Contents, Preface, Conference Organization

Cite as

13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{iacono:LIPIcs.FUN.2026.0,
  author =	{Iacono, John},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.0},
  URN =		{urn:nbn:de:0030-drops-257965},
  doi =		{10.4230/LIPIcs.FUN.2026.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.1

Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges

Authors: Abdelrahman Abdelmonsef, Xingyu Dong, Daniel Průša, Michael Wehar, and Chen Xu

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We investigate coding challenge problems related to finding a maximum (or minimum) size match for a predetermined two-dimensional pattern. We improve upon known runtime results by introducing new algorithms and refining existing algorithmic techniques. First, we present our main result which introduces a nearly quadratic time algorithm for the problem of finding a rectangular block within a matrix of maximum (or minimum) size containing only positive border entries which improves the prior cubic time solution. Then, we introduce a quadratic time and linear space algorithm for the problem of finding all rectangular blocks containing only positive border and empty interior entries. Finally, we present a log(n) factor improvement for detecting the largest length such that all square blocks in a matrix have their sums bounded by a given number.

Cite as

Abdelrahman Abdelmonsef, Xingyu Dong, Daniel Průša, Michael Wehar, and Chen Xu. Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abdelmonsef_et_al:LIPIcs.FUN.2026.1,
  author =	{Abdelmonsef, Abdelrahman and Dong, Xingyu and Pr\r{u}\v{s}a, Daniel and Wehar, Michael and Xu, Chen},
  title =	{{Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{1:1--1:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.1},
  URN =		{urn:nbn:de:0030-drops-257203},
  doi =		{10.4230/LIPIcs.FUN.2026.1},
  annote =	{Keywords: Pattern Matching, Matrices, Discrete Algorithms}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.2

Man, These New York Times Games Are Hard! A Computational Perspective

Authors: Alessandro Giovanni Alberti, Flavio Chierichetti, Mirko Giacchini, Daniele Muscillo, Alessandro Panconesi, and Erasmo Tani

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper’s readership. In this paper, we bring the computational lens to the study of New York Times games and consider four of them not previously studied: Letter Boxed, Pips, Strands and Tiles. We show that these games can be just as hard as they are fun. In particular, we characterize the hardness of several variants of computational problems related to these popular puzzle games. For Letter Boxed, we show that deciding whether an instance is solvable is in general NP-Complete, while in some parameter settings it can be done in polynomial time. Similarly, for Pips we prove that deciding whether a puzzle has a solution is NP-Complete even in some restricted classes of instances. We then show that one natural computational problem arising from Strands is NP-Complete in most parameter settings. Finally, we demonstrate that deciding whether a Tiles puzzle is solvable with a single, uninterrupted combo requires polynomial time.

Cite as

Alessandro Giovanni Alberti, Flavio Chierichetti, Mirko Giacchini, Daniele Muscillo, Alessandro Panconesi, and Erasmo Tani. Man, These New York Times Games Are Hard! A Computational Perspective. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alberti_et_al:LIPIcs.FUN.2026.2,
  author =	{Alberti, Alessandro Giovanni and Chierichetti, Flavio and Giacchini, Mirko and Muscillo, Daniele and Panconesi, Alessandro and Tani, Erasmo},
  title =	{{Man, These New York Times Games Are Hard! A Computational Perspective}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.2},
  URN =		{urn:nbn:de:0030-drops-257219},
  doi =		{10.4230/LIPIcs.FUN.2026.2},
  annote =	{Keywords: NP-Hardness, Puzzles, Games, New York Times, Pips, Letter Boxed, Strands, Tiles}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.3

Hive Is PSPACE-Hard

Authors: Daniël I. Andel and Benjamin G. Rin

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Hive is an abstract strategy game played on a table with hexagonal pieces. First published in 2001, it was and continues to be highly popular among both casual and competitive players. In this paper, we show that for a suitably generalized version of the game, the computational problem of determining whether a given player in an arbitrary position has a winning strategy is PSPACE-hard. We do this by reduction from Formula Game, which is first reduced to an intermediate problem we call Formula Game Geography, after which the latter is reduced to our decision problem.

Cite as

Daniël I. Andel and Benjamin G. Rin. Hive Is PSPACE-Hard. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andel_et_al:LIPIcs.FUN.2026.3,
  author =	{Andel, Dani\"{e}l I. and Rin, Benjamin G.},
  title =	{{Hive Is PSPACE-Hard}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.3},
  URN =		{urn:nbn:de:0030-drops-257221},
  doi =		{10.4230/LIPIcs.FUN.2026.3},
  annote =	{Keywords: Computational complexity, Combinatorial games, Hive, PSPACE-hardness, Formula Game, Generalized Geography}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.4

The Closed Hull Game and the Closed Interval Game

Authors: Samuel N. Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, and Rudini Sampaio

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Given a set S of vertices in a graph G, its geodesic interval is the set I(S) containing S and all vertices on a shortest path between vertices of S. A set S is convex if I(S) = S. Moreover, the convex hull ℋ(S) of S is the smallest convex set containing S. In 1984, Harary introduced convexity games where two players, Alice and Bob, alternately select vertices of a graph G = (V,E) such that, if the set of already selected vertices is S, the next player can only select a vertex in V ⧵ I(S) (closed interval game) or in V ⧵ ℋ(S) (closed hull game). Normal and misère versions of these games have been studied and here, we introduced the optimization variants of them. Formally, given a graph G and k ∈ ℕ, Alice wins if the game ends after at most k vertices have been selected and Bob wins otherwise. The corresponding problem consists of determining which player has a winning strategy. We prove that the closed interval optimization game is PSPACE-complete in graphs with diameter 4 and that the closed hull optimization game is NP-hard in bipartite graphs and in split graphs. On the positive side, we prove that both games can be solved in polynomial time in trees and that the closed hull optimization game can be solved in polynomial time in cobipartite graphs. We conjecture that the closed interval optimization game is NP-hard in cobipartite graphs and that the closed hull optimization game is PSPACE-complete in general graphs.

Cite as

Samuel N. Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, and Rudini Sampaio. The Closed Hull Game and the Closed Interval Game. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.FUN.2026.4,
  author =	{Ara\'{u}jo, Samuel N. and Benevides, Fabr{\'\i}cio and Martins, Nicolas and Nisse, Nicolas and Sampaio, Rudini},
  title =	{{The Closed Hull Game and the Closed Interval Game}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.4},
  URN =		{urn:nbn:de:0030-drops-257232},
  doi =		{10.4230/LIPIcs.FUN.2026.4},
  annote =	{Keywords: Combinatorial games in graphs, graph convexity, PSPACE}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.5

Token Positional Games

Authors: Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

The classical Maker-Breaker positional game is played on a board which is a hypergraph ℋ, with two players, Maker and Breaker, alternately claiming vertices of ℋ until all the vertices are claimed. When the game ends, Maker wins if she has claimed all the vertices of some edge of ℋ; otherwise, Breaker wins. Playing this game in real life can be done by placing tokens on the vertices of the board. In this paper, we study the unfortunate case in which one or both players do not have enough tokens to cover all the vertices and, as such, will have to move their tokens around at some point instead of placing new ones. There may be a bias, in that Maker and Breaker do not necessarily have the same amount of tokens. The present paper initiates the study of this generalization of positional games, called token positional games. A particularly interesting case is when Maker has a winning strategy in the classical game: what is the lowest number of tokens with which she still wins against Breaker’s unlimited stock? We notably show that, for k-uniform hypergraphs on an arbitrarily large number n of vertices, this number equals k if k ∈ {2,3} but can vary from k to Ω(n) if k ≥ 4. From an algorithmic point of view, PSPACE-hardness in general is inherited from classical positional games, but we get a polynomial-time algorithm to solve the case where Breaker only has one token. We also establish EXPTIME-completeness for a "token sliding" variation of the game.

Cite as

Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid. Token Positional Games. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bagan_et_al:LIPIcs.FUN.2026.5,
  author =	{Bagan, Guillaume and Deschamps, Quentin and Galliot, Florian and Mikala\v{c}ki, Mirjana and Oijid, Nacim},
  title =	{{Token Positional Games}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.5},
  URN =		{urn:nbn:de:0030-drops-257240},
  doi =		{10.4230/LIPIcs.FUN.2026.5},
  annote =	{Keywords: positional games, token games, hypergraphs, algorithmic complexity}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.6

Ferry Cover with Connectivity Constraints

Authors: Niranjan Balachandran, Ankita Dargad, Urban Larsson, Neeldhara Misra, and Umesh Shankar

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

The classical Ferry Cover problem asks for the minimum boat capacity needed to transport all vertices of a graph across a river such that no edge remains on either bank at any time - a requirement that the banks induce stable (independent) sets. We study a natural generalization in which the banks must satisfy an arbitrary graph property. For hereditary properties such as acyclicity or planarity, we show that the structural characterization of small-boat and large-boat graphs established by Csorba, Hurkens, and Woeginger extends directly. We then turn to the connected-bank variant, where the property of interest - connectedness - is not hereditary: both banks must induce connected subgraphs throughout the transfer. We provide a complete characterization of graphs that can be transferred with a boat of size one (boat-1 graphs): a connected graph is boat-1 if and only if its block-cut tree is a path. This characterization yields a linear-time recognition algorithm. As a consequence, we show that every biconnected graph is boat-1, since such graphs admit an st-numbering. We also develop an efficient algorithm for determining the boat number of trees. Our work opens new directions for river-crossing problems under non-hereditary bank constraints.

Cite as

Niranjan Balachandran, Ankita Dargad, Urban Larsson, Neeldhara Misra, and Umesh Shankar. Ferry Cover with Connectivity Constraints. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{balachandran_et_al:LIPIcs.FUN.2026.6,
  author =	{Balachandran, Niranjan and Dargad, Ankita and Larsson, Urban and Misra, Neeldhara and Shankar, Umesh},
  title =	{{Ferry Cover with Connectivity Constraints}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.6},
  URN =		{urn:nbn:de:0030-drops-257253},
  doi =		{10.4230/LIPIcs.FUN.2026.6},
  annote =	{Keywords: ferry cover, river crossing, block-cut tree, st-numbering, hereditary graph property, connectivity}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.7

Nemesis, an Escape Game in Graphs

Authors: Pierre Bergé, Antoine Dailly, and Yan Gerard

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We define a new escape game in graphs that we call Nemesis. The game is played on a graph having a subset of vertices labeled as exits and the goal of one of the two players, called the fugitive, is to reach one of these exit vertices. The second player, i.e. the fugitive adversary, is called the Nemesis. Her goal is to trap the fugitive in a connected component which does not contain any exit. At each round of the game, the fugitive moves from one vertex to an adjacent vertex. Then the Nemesis deletes one edge anywhere in the graph. The game ends when either the fugitive reached an exit or when he is in a connected component that does not contain any exit. In trees and graphs of maximum degree bounded by 3, Nemesis can be solved in linear time. For arbitrary graphs, we show that Nemesis is PSPACE-complete, and that it is NP-hard on planar multigraphs. We extend our results to the related Cat Herding problem, proving its PSPACE-completeness.

Cite as

Pierre Bergé, Antoine Dailly, and Yan Gerard. Nemesis, an Escape Game in Graphs. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berge_et_al:LIPIcs.FUN.2026.7,
  author =	{Berg\'{e}, Pierre and Dailly, Antoine and Gerard, Yan},
  title =	{{Nemesis, an Escape Game in Graphs}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.7},
  URN =		{urn:nbn:de:0030-drops-257261},
  doi =		{10.4230/LIPIcs.FUN.2026.7},
  annote =	{Keywords: Graphs, Evasion and Pursuit Games, PSPACE-completeness, Quantified SAT, Canadian Traveler Problem, Cat Herding Problem}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.8

Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception

Authors: Jean-Claude Bermond, Michel Cosnard, Frédéric Havet, Takako Kodate, and Stéphane Pérennes

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We introduce and study the directed grabbing game, a directed variation of the graph grabbing game played by two players Alice and Bob on a weighted acyclic digraph D. Alice plays first and then they play alternately. At a given odd (resp. even) move, Alice (resp. Bob) chooses a sink, that is a vertex of out-degree 0, grabs the weight (olives) on it and then removes the vertex. The aim of each player is to grab a maximum weight, i.e. a maximum number of olives. This game is inspired by the behaviour that guests are expected to adopt during a reception or cocktail party. We first consider the case where hors d'oeuvre are arranged on slightly spaced parallel lines, such that politeness allows one to take the first hors d'oeuvre from each line. This corresponds to the directed grabbing game on a union of disjoint directed paths. We give an algorithm that, given a weighted digraph D of order n which is the union of q disjoint directed paths, computes an optimal play in O(nlog q) time. Then we consider the "pissaladière case" where the digraph D is a directed (p× q)-grid. We show that, depending on the parity of pq, one player, called Content, has a strategic advantage. Specifically, Content is Alice when pq is odd and Bob when pq is even. We present some strategies that enable Content to remove some large sets of vertices (of order pq/2) in directed grids. We then derive that Content can remove any given vertex that is not in the border of the grid. Finally, in the case where each vertex contains either zero or one olive, we prove that Content can secure the grabbing of around one third of the olives.

Cite as

Jean-Claude Bermond, Michel Cosnard, Frédéric Havet, Takako Kodate, and Stéphane Pérennes. Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2026.8,
  author =	{Bermond, Jean-Claude and Cosnard, Michel and Havet, Fr\'{e}d\'{e}ric and Kodate, Takako and P\'{e}rennes, St\'{e}phane},
  title =	{{Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.8},
  URN =		{urn:nbn:de:0030-drops-257273},
  doi =		{10.4230/LIPIcs.FUN.2026.8},
  annote =	{Keywords: grabbing games, paths, directed grids}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.9

MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

Authors: Charles Bouillaguet and Orel Cosseron

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

A recursive maze is a maze that contains copies of itself (that themselves contain copies of themselves, etc.). To exit the maze or reach the goal, each recursive block that has been entered must be exited. These once-popular puzzles are difficult to solve by hand, and this begs for an algorithmic solution. It has been observed many times in the past that a recursive maze can be represented by a deterministic pushdown automaton. Finding a path, possibly the shortest, that leads to an exit therefore reduces to finding a word in a context-free language described by such an automaton. The problem is well-known to be decidable, and there is a classical algorithm for this task. We present a new algorithm, Midterm, with improved complexity compared to existing solutions. Midterm improves on a previous attempt called Longterm (Obviously Not a Good Technique to Exit Recursive Mazes).

Cite as

Charles Bouillaguet and Orel Cosseron. MIDTERM Is a Deterministic Technique to Exit Recursive Mazes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bouillaguet_et_al:LIPIcs.FUN.2026.9,
  author =	{Bouillaguet, Charles and Cosseron, Orel},
  title =	{{MIDTERM Is a Deterministic Technique to Exit Recursive Mazes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.9},
  URN =		{urn:nbn:de:0030-drops-257280},
  doi =		{10.4230/LIPIcs.FUN.2026.9},
  annote =	{Keywords: Recursive maze, pushdown automaton, reachability, context-free grammar, graph rewriting}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.10

77 Shades of Grey

Authors: Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Bruce Wayne contacted us to help him develop a new surveillance technology for dark environments such as caves, using a swarm of Unmanned Aerial Vehicles (UAVs), called Batdroids. A Batdroid has no chirality, limited visibility, and a perfect clock to synchronize with the others. A Batdroid can produce 77 shades of grey in dark mode and four colors in light mode. In this paper, we propose two algorithms using three Batdroids to perpetually explore a finite 3D grid modeling a cave. The first algorithm operates in darkness, uses 77 shades of grey, and requires visibility range one. The second operates in light, uses four colors and visibility range two. We also prove that three is the optimal number of Batdroids required to solve Bruce Wayne’s challenge.

Cite as

Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. 77 Shades of Grey. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.FUN.2026.10,
  author =	{Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa},
  title =	{{77 Shades of Grey}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.10},
  URN =		{urn:nbn:de:0030-drops-257294},
  doi =		{10.4230/LIPIcs.FUN.2026.10},
  annote =	{Keywords: Mobile robots, grid exploration, perpetual exploration}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.11

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle

Authors: Matteo Caporrella and Stefano Leucci

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We study the Torus Puzzle, a solitaire game in which the elements of an input m × n matrix need to be rearranged into a target configuration via a sequence of unit rotations (i.e., circular shifts) of rows and/or columns. Amano et al. proposed a more permissive variant of the above puzzle, where each row and column rotation can shift the involved elements by any amount of positions. The number of rotations needed to solve the original and the permissive variants of the puzzle are respectively known as the push number and the drag number, where the latter is always smaller than or equal to the former and admits an existential lower bound of Ω(mn). While this lower bound is matched by an O(mn) upper bound, the push number is not so well understood. Indeed, to the best of our knowledge, only an O(mn ⋅ max{m, n}) upper bound is currently known. In this paper, we provide an algorithm that solves the Torus Puzzle using O(mn ⋅ log max {m, n}) unit rotations in a model that is more restricted than that of the original puzzle. This implies a corresponding upper bound on the push number and reduces the gap between the known upper and lower bounds from Θ(max{m,n}) to Θ(log max{m, n}).

Cite as

Matteo Caporrella and Stefano Leucci. An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caporrella_et_al:LIPIcs.FUN.2026.11,
  author =	{Caporrella, Matteo and Leucci, Stefano},
  title =	{{An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.11},
  URN =		{urn:nbn:de:0030-drops-257307},
  doi =		{10.4230/LIPIcs.FUN.2026.11},
  annote =	{Keywords: Torus puzzle, Push number, Permutation puzzles}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.12

A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles

Authors: Brynmor Chapman, Lily Chung, Erik D. Demaine, Yota Irino, Della Hendrickson, Tonan Kamata, and Ryuhei Uehara

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

In arithmetic puzzles, a partially specified arithmetic expression must be completed to make the computation valid. Arithmetical restoration puzzles require filling in missing digits, while cryptarithms involve assigning digits to letters. The Japanese term mushikui-zan ("bookwormed arithmetic") commonly refers to arithmetical restorations, where we imagine the missing digits have been eaten by a bookworm. Puzzle creator Yousuke Ikeda proposed a new type of puzzle in which a previously designed bookwormed arithmetic with multiplication - known to have a unique solution - has itself been "bookwormed", that is, partially erased. The goal is to restore the specified blanks so that the resulting bookwormed puzzle again has a unique solution. We further generalize this framework: for each k ≥ 2, we define level-k puzzles as those in which type-k blanks must be filled to make the resulting level-(k{-}1) puzzle uniquely solvable. We study the level-k versions of the Boolean satisfiability problem, and show that they form a hierarchy of Σ^P_k-complete decision problems, tightly matching the levels of the polynomial hierarchy. As applications, we show that the level-k arithmetical restoration problem with multiplication is Σ^P_k-complete, as is the level-k cryptarithm problem. On the positive side, we show that level-2 arithmetical restoration puzzles with addition are solvable in polynomial time.

Cite as

Brynmor Chapman, Lily Chung, Erik D. Demaine, Yota Irino, Della Hendrickson, Tonan Kamata, and Ryuhei Uehara. A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.FUN.2026.12,
  author =	{Chapman, Brynmor and Chung, Lily and Demaine, Erik D. and Irino, Yota and Hendrickson, Della and Kamata, Tonan and Uehara, Ryuhei},
  title =	{{A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.12},
  URN =		{urn:nbn:de:0030-drops-257311},
  doi =		{10.4230/LIPIcs.FUN.2026.12},
  annote =	{Keywords: arithmetical restoration, cryptarithms, polynomial hierarchy, uniqueness quantifier, puzzle complexity}
}

215 Search Results for "Iacono, John"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message