13 Search Results for "Nisse, Nicolas"

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.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.24
On the Complexity of the Maker-Breaker Happy Vertex Game

Authors: Mathieu Hilaire, Perig Montfort, and Nacim Oijid

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

Abstract
Given a c-colored graph G, a vertex v of G is said to be happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li [Peng Zhang and Angsheng Li, 2015] to compute the homophily of a graph. Eto, Fujimoto, Kiya, Matsushita, Miyano, Murao and Saitoh [Hiroshi Eto et al., 2025] introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker domination game introduced by Duchene, Gledel, Parreau and Renault [Duchene et al., 2020], as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games [Bagan et al., 2024]. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests.
Cite as

Mathieu Hilaire, Perig Montfort, and Nacim Oijid. On the Complexity of the Maker-Breaker Happy Vertex Game. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hilaire_et_al:LIPIcs.FUN.2026.24,
  author =	{Hilaire, Mathieu and Montfort, Perig and Oijid, Nacim},
  title =	{{On the Complexity of the Maker-Breaker Happy Vertex Game}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-257434},
  doi =		{10.4230/LIPIcs.FUN.2026.24},
  annote =	{Keywords: Maker-Breaker game, Domination game, happy vertex game, scoring game, complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.7
Mobile Byzantine Agreement in a Trusted World

Authors: Bo Pan and Maria Potop-Butucaru

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on two representative models: Garay’s and Buhrman’s models. In Garay’s model, when a process has been left by the Byzantine agent, it enters a cured state, is aware of its condition, and can remain silent for a round to prevent the dissemination of incorrect information. In Buhrman’s model, a Byzantine agent moves together with the message. It has been shown that solving Byzantine Agreement requires at least 4t + 1 processes in Garay’s model, and at least 3t + 1 in Buhrman’s model. In this paper, we aim to increase the tolerance to mobile Byzantine agents by integrating a trusted counter abstraction into both models. This abstraction prevents nodes from equivocating. In the new models, we prove that at least 3t+1, respectively 2t+1 processors are needed to tolerate t mobile Byzantine agents. Furthermore, we propose novel Mobile Byzantine Agreement algorithms that match these new lower bounds for both Garay’s and Buhrman’s models, achieving agreement in 𝒪(n) synchronous rounds.
Cite as

Bo Pan and Maria Potop-Butucaru. Mobile Byzantine Agreement in a Trusted World. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pan_et_al:LIPIcs.OPODIS.2025.7,
  author =	{Pan, Bo and Potop-Butucaru, Maria},
  title =	{{Mobile Byzantine Agreement in a Trusted World}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.7},
  URN =		{urn:nbn:de:0030-drops-251809},
  doi =		{10.4230/LIPIcs.OPODIS.2025.7},
  annote =	{Keywords: Byzantine Agreement, Mobile Faults, Trusted Abstractions}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.22
The Complexity Landscape of Dynamic Distributed Subgraph Finding

Authors: Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, and Mingyang Yang

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Bonne and Censor-Hillel (ICALP 2019) initiated the study of distributed subgraph finding in dynamic networks of limited bandwidth. For the case where the target subgraph is a clique, they determined the tight bandwidth complexity bounds in nearly all settings. However, several open questions remain, and very little is known about finding subgraphs beyond cliques. In this work, we consider these questions and explore subgraphs beyond cliques in the deterministic setting. For finding cliques, we establish an Ω(log log n) bandwidth lower bound for one-round membership-detection under edge insertions only and an Ω(log log log n) bandwidth lower bound for one-round detection under both edge insertions and node insertions. Moreover, we demonstrate new algorithms to show that our lower bounds are tight in bounded-degree networks when the target subgraph is a triangle. Prior to our work, no lower bounds were known for these problems. For finding subgraphs beyond cliques, we present a complete characterization of the bandwidth complexity of the membership-listing problem for every target subgraph, every number of rounds, and every type of topological change: node insertions, node deletions, edge insertions, and edge deletions. We also show partial characterizations for one-round membership-detection and listing.
Cite as

Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, and Mingyang Yang. The Complexity Landscape of Dynamic Distributed Subgraph Finding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.DISC.2025.22,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Chen, Yanyu and Mishra, Gopinath and Yang, Mingyang},
  title =	{{The Complexity Landscape of Dynamic Distributed Subgraph Finding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.22},
  URN =		{urn:nbn:de:0030-drops-248399},
  doi =		{10.4230/LIPIcs.DISC.2025.22},
  annote =	{Keywords: Distributed algorithms, dynamic algorithms, subgraph finding}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.12
Distributed Computation with Local Advice

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed Computation with Local Advice. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.12,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Nowicki, Krzysztof and Olivetti, Dennis and Rotenberg, Eva and Suomela, Jukka},
  title =	{{Distributed Computation with Local Advice}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.12},
  URN =		{urn:nbn:de:0030-drops-248295},
  doi =		{10.4230/LIPIcs.DISC.2025.12},
  annote =	{Keywords: Distributed graph algorithms, LOCAL model, computation with advice, locally checkable labeling problems, proof labeling schemes, locally checkable proofs, graph coloring, exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.37
Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology

Authors: Henrique Ennes and Clément Maria

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M' with the same quantum invariant, such that M' is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton [Samperton, 2023].
Cite as

Henrique Ennes and Clément Maria. Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ennes_et_al:LIPIcs.ESA.2025.37,
  author =	{Ennes, Henrique and Maria, Cl\'{e}ment},
  title =	{{Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.37},
  URN =		{urn:nbn:de:0030-drops-245057},
  doi =		{10.4230/LIPIcs.ESA.2025.37},
  annote =	{Keywords: 3-manifold, Heegaard splitting, Hempel distance, Quantum invariant, polynomial time reduction}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.12
Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings

Authors: Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).
Cite as

Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo. Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ooshita_et_al:LIPIcs.OPODIS.2024.12,
  author =	{Ooshita, Fukuhito and Kitamura, Naoki and Eguchi, Ryota and Inoue, Michiko and Kakugawa, Hirotsugu and Kamei, Sayaka and Shibata, Masahiro and Sudo, Yuichi},
  title =	{{Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.12},
  URN =		{urn:nbn:de:0030-drops-225486},
  doi =		{10.4230/LIPIcs.OPODIS.2024.12},
  annote =	{Keywords: mobile robots, crash faults, LCM model, exploration}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.42
Recontamination Helps a Lot to Hunt a Rabbit

Authors: Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, and Nicolas Nisse

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing h(G) remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G)+1 for any graph G with pathwidth pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant, is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e., that monotonicity does not help. In particular, we show that, for every k ≥ 3, there exists a tree T with h(T) = 2 and mh(T) = k. We conclude by proving that computing h (resp., mh) is FPT parameterised by the minimum size of a vertex cover.
Cite as

Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, and Nicolas Nisse. Recontamination Helps a Lot to Hunt a Rabbit. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dissaux_et_al:LIPIcs.MFCS.2023.42,
  author =	{Dissaux, Thomas and Fioravantes, Foivos and Gahlawat, Harmender and Nisse, Nicolas},
  title =	{{Recontamination Helps a Lot to Hunt a Rabbit}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.42},
  URN =		{urn:nbn:de:0030-drops-185763},
  doi =		{10.4230/LIPIcs.MFCS.2023.42},
  annote =	{Keywords: Hunter and Rabbit, Monotonicity, Graph Searching}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.18
Space and Time Trade-Off for the k Shortest Simple Paths Problem

Authors: Ali Al Zoobi, David Coudert, and Nicolas Nisse

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a vertex s to a vertex t in a digraph. Yen (1971) proposed the first algorithm with the best known theoretical complexity of O(kn(m+n log n)) for a digraph with n vertices and m arcs. Since then, the problem has been widely studied from an algorithm engineering perspective, and impressive improvements have been achieved. In particular, Kurz and Mutzel (2016) proposed a sidetracks-based (SB) algorithm which is currently the fastest solution. In this work, we propose two improvements of this algorithm. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees. We did experiments on some road networks of the 9th DIMAC'S challenge with up to about half a million nodes and one million arcs. Our computational results show an average speed up by a factor of 1.5 to 2 with a similar working memory consumption as SB. We then propose a second algorithm enabling to significantly reduce the working memory at the cost of an increase of the running time (up to two times slower). Our experiments on the same data set show, on average, a reduction by a factor of 1.5 to 2 of the working memory.
Cite as

Ali Al Zoobi, David Coudert, and Nicolas Nisse. Space and Time Trade-Off for the k Shortest Simple Paths Problem. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alzoobi_et_al:LIPIcs.SEA.2020.18,
  author =	{Al Zoobi, Ali and Coudert, David and Nisse, Nicolas},
  title =	{{Space and Time Trade-Off for the k Shortest Simple Paths Problem}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.18},
  URN =		{urn:nbn:de:0030-drops-120925},
  doi =		{10.4230/LIPIcs.SEA.2020.18},
  annote =	{Keywords: k shortest simple paths, graph algorithm, space-time trade-off}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.22
Study of a Combinatorial Game in Graphs Through Linear Programming

Authors: Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.
Cite as

Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes. Study of a Combinatorial Game in Graphs Through Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ISAAC.2017.22,
  author =	{Cohen, Nathann and Mc Inerney, Fionn and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Study of a Combinatorial Game in Graphs Through Linear Programming}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.22},
  URN =		{urn:nbn:de:0030-drops-82254},
  doi =		{10.4230/LIPIcs.ISAAC.2017.22},
  annote =	{Keywords: Turn-by-turn games in graphs, Graph algorithms, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.10
Spy-Game on Graphs

Authors: Nathann Cohen, Mathieu Hilaire, Nícolas A. Martins, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We define and study the following two-player game on a graph G. Let k in N^*. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s in N^* is his speed. Then, each guard may move along one edge. The spy and the guards may occupy same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than d in N (a predefined distance) from every guard. Can the spy win against k guards? Similarly, what is the minimum distance d such that k guards may ensure that at least one of them remains at distance at most d from the spy? This game generalizes two well-studied games: Cops and robber games (when s=1) and Eternal Dominating Set (when s is unbounded). We consider the computational complexity of the problem, showing that it is NP-hard and that it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards and the required distance d when G is a path or a cycle. Our main result is that there exists beta>0 such that Omega(n^{1+beta}) guards are required to win in any n*n grid.
Cite as

Nathann Cohen, Mathieu Hilaire, Nícolas A. Martins, Nicolas Nisse, and Stéphane Pérennes. Spy-Game on Graphs. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.FUN.2016.10,
  author =	{Cohen, Nathann and Hilaire, Mathieu and Martins, N{\'\i}colas A. and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Spy-Game on Graphs}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.10},
  URN =		{urn:nbn:de:0030-drops-58782},
  doi =		{10.4230/LIPIcs.FUN.2016.10},
  annote =	{Keywords: graph, two-player games, cops and robber games, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.75
Weighted Coloring in Trees

Authors: Julio Araujo, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.
Cite as

Julio Araujo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 75-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.STACS.2014.75,
  author =	{Araujo, Julio and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Weighted Coloring in Trees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{75--86},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.75},
  URN =		{urn:nbn:de:0030-drops-44484},
  doi =		{10.4230/LIPIcs.STACS.2014.75},
  annote =	{Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3-SAT}
}
  • Refine by Type
  • 13 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 4 2025
  • 1 2023
  • 1 2020
  • 1 2017
  • Show More...

  • Refine by Author
  • 6 Nisse, Nicolas
  • 3 Pérennes, Stéphane
  • 2 Cohen, Nathann
  • 2 Hilaire, Mathieu
  • 1 Al Zoobi, Ali
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Algorithmic game theory
  • Show More...

  • Refine by Keyword
  • 2 complexity
  • 1 3-SAT
  • 1 3-manifold
  • 1 Byzantine Agreement
  • 1 Canadian Traveler Problem
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact