Nicolas Nisse

TCS Journal 2026 Journal Article

Pathlength of outerplanar graphs

• Thomas Dissaux
• Nicolas Nisse

A path-decomposition of a graph G = ( V, E ) is a sequence of subsets of V, called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance (in G) between two vertices that belong to a same bag and the pathlength, denoted by pℓ(G), of G is the smallest length of its path-decompositions. This parameter has been studied for its algorithmic applications for several classical metric problems like the minimum eccentricity shortest path problem, the line-distortion problem, etc. However, deciding if the pathlength of a graph G is at most 2 is NP-complete, and the best known approximation algorithm has a ratio 2 (there is no c-approximation with c < 3 2 unless P = N P ). In this work, we focus on the study of the pathlength of simple sub-classes of planar graphs. We start by designing a linear-time algorithm that computes the pathlength of trees. Then, we show that the pathlength of cycles with n vertices is equal to ⌊ n 2 ⌋. Our main result is a ( + 1 ) -approximation algorithm for the pathlength of outerplanar graphs. This algorithm is based on a characterization of almost optimal (of length at most p ℓ ( G ) + 1 ) path-decompositions of outerplanar graphs.

I&C Journal 2025 Journal Article

Further results on the Hunters and Rabbit game through monotonicity

• Thomas Dissaux
• Foivos Fioravantes
• Harmender Gahlawat
• Nicolas Nisse

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 not shot, must move to a neighbouring vertex. The Rabbit player wins if and only if it is not shot indefinitely. The hunter number h ( G ) of a graph G is the minimum k such that the Hunter player has a winning strategy. We propose a notion of monotonicity, embodied in the monotone hunter number m h ( G ), for this game imposing that a vertex that has already been shot “must not host the rabbit anymore”. We show that p w ( G ) ≤ m h ( G ) ≤ p w ( G ) + 1 for any graph G with pathwidth p w ( G ), implying that computing, or even approximating, m h ( G ) is NP-hard. Then, we show that m h ( G ) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which relate the monotone hunter number with the pathwidth. In all these cases, we either specify the hunter number or show that there may be an arbitrary gap between h and mh, i. e. , that monotonicity does not help. In particular, for every k ≥ 3, we construct a tree T with h ( T ) = 2 and m h ( T ) = k. We conclude by proving that computing h (resp. , mh) is FPT parameterised by the vertex cover number.

TCS Journal 2025 Journal Article

The Convex Set Forming Game

• Caroline Brosse
• Nicolas Martins
• Nicolas Nisse
• Rudini Sampaio

In 1984, Frank Harary introduced the first graph convexity game, focused on the geodesic convexity. A set S ⊆ V of vertices of a graph G = ( V, E ) is convex if every shortest path between two vertices of S is also included in S. We introduce the Convex Set Forming Game CFG: two players alternately select vertices in such a way that the set of selected vertices is always a convex set. In the normal (resp. , misère) variant, the last player to be able to select a vertex wins (resp. , loses). We also define a new graph invariant gc ( G ) as the largest integer k such that the first player has a strategy ensuring that, at the end of the game, at least k vertices of the graph G have been selected. We first show that the problems of deciding the outcome (does the first player win?) of the game in both variants (normal and misère), as well as the problem of deciding whether gc ( G ) ≥ k, are PSPACE-complete. As a by-product, we prove that the optimization variant of the classical Kayles game is PSPACE-complete. Then, we focus on convexable graphs, i. e. , n-node graphs G for which gc ( G ) = n. For this purpose, we say that a set S = { v 1, ⋯, v | S | } ⊆ V in a graph G admits a Convex Elimination Ordering (CEO) if { v 1, ⋯, v i } is convex for every 1 ≤ i ≤ | S |. We show that the class of graphs whose vertex-set admits a CEO coincides with the chordal graphs and that this class strictly contains the convexable graphs. Moreover, every graph which is Ptolemaic (distance-hereditary chordal) or unit interval is convexable. Finally, we give a polynomial-time algorithm for computing a largest set admitting a CEO in outerplanar graphs, which gives upper bounds on gc ( G ) in outerplanar graphs G.

TCS Journal 2024 Journal Article

Preface to special issue on theory and applications of Graph Searching

• Spyros Angelopoulos
• Pierre Fraigniaud
• Nicolas Nisse
• Dimitrios M. Thilikos

MFCS Conference 2023 Conference Paper

Recontamination Helps a Lot to Hunt a Rabbit

• Thomas Dissaux
• Foivos Fioravantes
• Harmender Gahlawat
• Nicolas Nisse

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.

TCS Journal 2023 Journal Article

The Maker-Breaker Largest Connected Subgraph game

• Julien Bensmail
• Foivos Fioravantes
• Fionn Mc Inerney
• Nicolas Nisse
• Nacim Oijid

Given a graph G and k ∈ N, we introduce the following game played in G. Each round, Alice colours an uncoloured vertex of G red, and then Bob colours one blue (if any remain). Once every vertex is coloured, Alice wins if there is a connected red component of order at least k, and otherwise, Bob wins. This is a Maker-Breaker version of the Largest Connected Subgraph game introduced in [Bensmail et al. , The largest connected subgraph game, Algorithmica 84 (9) (2022) 2533–2555]. We want to compute c g ( G ), which is the maximum k such that Alice wins in G, regardless of Bob's strategy. Given a graph G and k ∈ N, we prove that deciding whether c g ( G ) ≥ k is PSPACE-complete, even if G is a bipartite, split, or planar graph. To better understand the Largest Connected Subgraph game, we then focus on A-perfect graphs, which are the graphs G for which c g ( G ) = ⌈ | V ( G ) | / 2 ⌉, i. e. , those in which Alice can ensure that the red subgraph is connected. We give sufficient conditions, in terms of the minimum and maximum degrees or the number of edges, for a graph to be A-perfect. Also, we show that, for any d ≥ 4, there are arbitrarily large A-perfect d-regular graphs, but no cubic graph with order at least 18 is A-perfect. Lastly, we show that c g ( G ) is computable in linear time when G is a P 4 -sparse graph (a superclass of cographs).

TCS Journal 2019 Journal Article

Preface to special issue on Theory and Applications of Graph Searching

• Spyros Angelopoulos
• Nicolas Nisse
• Dimitrios M. Thilikos

TCS Journal 2018 Journal Article

Spy-game on graphs: Complexity and simple topologies

• Nathann Cohen
• Nícolas A. Martins
• Fionn Mc Inerney
• Nicolas Nisse
• Stéphane Pérennes
• Rudini Sampaio

We define and study the following two-player game on a graph G. Let k ∈ 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 ∈ N ⁎ is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy has to escape the surveillance of the guards, i. e. , must reach a vertex at distance more than d ∈ 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 (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.

I&C Journal 2017 Journal Article

Exclusive graph searching vs. pathwidth

• Euripides Markou
• Nicolas Nisse
• Stéphane Pérennes

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard.

TCS Journal 2016 Journal Article

Forewords: Special issue on Theory and Applications of Graph Searching Problems

• Fedor V. Fomin
• Pierre Fraigniaud
• Nicolas Nisse
• Dimitrios M. Thilikos

TCS Journal 2015 Journal Article

Data gathering and personalized broadcasting in radio grids with interference

• Jean-Claude Bermond
• Bi Li
• Nicolas Nisse
• Hervé Rivano
• Min-Li Yu

In the gathering problem, a particular node in a graph, the base station, aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbors (such an action is called a call). However, a node cannot send and receive a message during the same step. Moreover, the communication is subject to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most d I from the other receiver. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i. e. , minimizing the number of steps (called makespan). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints. In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with d I ∈ { 0, 1, 2 }. In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when d I = 0. If no messages are “close” to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when d I = 0, 4 when d I = 2, and 3 when both d I = 1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting.

TCS Journal 2015 Journal Article

Non-deterministic graph searching in trees

• Omid Amini
• David Coudert
• Nicolas Nisse

Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q ≥ 0, the q-limited search number, s q ( G ), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 ( G ) corresponds to the pathwidth of a graph G, and s ∞ ( G ) to its treewidth. Determining s q ( G ) is NP-complete for any fixed q ≥ 0 in general graphs and s 0 ( T ) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q > 0. We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0, 1, and at most twice s q for any q ≥ 2 (for any graph G). Our main result is a polynomial time algorithm that computes rs q ( T ) for any tree T and any q ≥ 0. This provides a 2-approximation of s q ( T ) for any tree T, and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest.

TCS Journal 2014 Journal Article

To satisfy impatient Web surfers is hard

• Fedor V. Fomin
• Frédéric Giroire
• Alain Jean-Marie
• Dorian Mazauric
• Nicolas Nisse

Prefetching is a basic mechanism for faster data access and efficient computing. An important issue in prefetching is the trade-off between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while a Web surfer is surfing. Since the Web surfer follows the hyperlinks in an unpredictable way, the choice of the Web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching that ensures that all documents accessed by the Web surfer have previously been loaded in the cache. We model this problem as a two-player game similar to Cops and Robber Games in graphs. Let k ⩾ 1 be any integer. The first player, a fugitive, starts on a marked vertex of a (di)graph G. The second player, an observer, marks at most k vertices, then the fugitive moves along one edge/arc of G to a new vertex, then the observer marks at most k vertices, etc. The fugitive wins if it enters an unmarked vertex, and the observer wins otherwise. The surveillance number of a (di)graph is the minimum k such that the observer marking at most k vertices at each step can win against any strategy of the fugitive. We also consider the connected variant of this game, i. e. , when a vertex can be marked only if it is adjacent to an already marked vertex. We study the computational complexity of the game. All our results hold for both variants, connected or unrestricted. We show that deciding whether the surveillance number of a chordal graph is at most 2 is NP-hard. We also prove that deciding if the surveillance number of a DAG is at most 4 is PSPACE-complete. Moreover, we show that the problem of computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms computing surveillance numbers of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization of the surveillance number.

I&C Journal 2012 Journal Article

Connected graph searching

• Lali Barrière
• Paola Flocchini
• Fedor V. Fomin
• Pierre Fraigniaud
• Nicolas Nisse
• Nicola Santoro
• Dimitrios M. Thilikos

In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i. e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on “the price of connectivity”, that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an n-vertex graph the ratio between the connected searching number and the non-connected one is O ( log n ) while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i. e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton–Strahler number.

TCS Journal 2012 Journal Article

Distributed computing of efficient routing schemes in generalized chordal graphs

• Nicolas Nisse
• Ivan Rapaport
• Karol Suchan

Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of k -chordal graphs, i. e. , graphs with no induced cycles of length more than k. In the class of k -chordal graphs, our routing scheme achieves an additive stretch of at most k − 1, i. e. , for all pairs of nodes, the length of the route never exceeds their distance plus k − 1. In order to compute the routing tables of any n -node graph with diameter D we propose a distributed algorithm which uses O ( log n ) -bit messages and takes O ( D ) time. The corresponding routing scheme achieves the stretch of k − 1 on k -chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes O ( min { Δ D, n } ) time, where Δ is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2 ( d − 1 ) log n bits per node of degree d.

TCS Journal 2011 Journal Article

Tradeoffs in process strategy games with application in the WDM reconfiguration problem

• Nathann Cohen
• David Coudert
• Dorian Mazauric
• Napoleão Nepomuceno
• Nicolas Nisse

We consider a variant of the graph searching games that models the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents aims at processing, or clearing, the vertices of a digraph D. We are interested in two different measures: (1) the total number of agents used, and (2) the total number of vertices occupied by an agent during the processing of D. These measures, respectively, correspond to the maximum number of simultaneous connections interrupted and to the total number of interruptions during a routing reconfiguration in a WDM network. Previous works have studied the problem of independently minimizing each of these parameters. In particular, the corresponding minimization problems are APX-hard, and the first one is known not to be in APX. In this paper, we give several complexity results and study tradeoffs between these conflicting objectives. In particular, we show that minimizing one of these parameters while the other is constrained is NP-complete. Then, we prove that there exist some digraphs for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even for a basic class of digraphs. On the other hand, we exhibit classes of graphs for which good tradeoffs can be achieved. We finally detail the relationship between this game and the routing reconfiguration problem. In particular, we prove that any instance of the processing game, i. e. any digraph, corresponds to an instance of the routing reconfiguration problem.

TCS Journal 2010 Journal Article

Pursuing a fast robber on a graph

• Fedor V. Fomin
• Petr A. Golovach
• Jan Kratochvíl
• Nicolas Nisse
• Karol Suchan

The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s ≤ 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.

TCS Journal 2009 Journal Article

Graph searching with advice

• Nicolas Nisse
• David Soguet

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70–84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i. e. , the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i. e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is Θ ( n log n ), where n is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G, using a total of O ( n log n ) bits, and a protocol using this labelling that enables the optimal number of searchers to clear G in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires Ω ( n log n ) bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.

TCS Journal 2008 Journal Article

Distributed chasing of network intruders

• Lélia Blin
• Pierre Fraigniaud
• Nicolas Nisse
• Sandrine Vial

Graph searching is one of the most popular tools for analyzing the chase for a powerful and hostile software agent (called the “intruder”), by a set of software agents (called the “searchers”) in a network. The existing solutions for the graph searching problem suffer however from a serious drawback: they are mostly centralized and assume a global synchronization mechanism for the searchers. In particular: (1) the search strategy for every network is computed based on the knowledge of the entire topology of the network, and (2) the moves of the searchers are controlled by a centralized mechanism that decides at every step which searcher has to move, and what movement it has to perform. This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without knowing the topology of the network in advance. It performs in an asynchronous environment, i. e. , it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most k + 1 searchers, where k is the minimum number of searchers required to clear the network in a monotone connected way using a strategy computed in the centralized and synchronous setting.

TCS Journal 2008 Journal Article

Monotonicity of non-deterministic graph searching

• Frédéric Mazoit
• Nicolas Nisse

In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i. e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack. Fomin et al. [F. V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS’05, 2005, pp. 364–375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.

I&C Journal 2008 Journal Article

Monotony properties of connected visible graph searching

• Pierre Fraigniaud
• Nicolas Nisse

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a. k. a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i. e. , at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i. e. , strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O ( log n ) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω ( log n ). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k ⩾ 4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k

MFCS Conference 2005 Conference Paper

Nondeterministic Graph Searching: From Pathwidth to Treewidth

• Fedor V. Fomin
• Pierre Fraigniaud
• Nicolas Nisse

Abstract We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game- theoretic approach and graph decompositions called q-branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q -branched tree decompositions. The equivalence between nondeterministic graph searching and q -branched tree decomposition enables us to design an exact (exponential time) algorithm computing q -branched treewidth for all q ≥ 0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.