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. It is known that the monotone connected
visible search number of an n-node graph is at most O(logn) 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 Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for
connected visible search. Precisely, we describe an infinite family of graphs for which any monotone connected visible search
strategy for any graph in this family requires strictly more searchers than the connected visible search number of the graph.
Keywords Graph Searching - Treewidth - Pathwidth
Both authors received additional supports from the project “PairAPair” of the ACI Masses de Données, from the project “Fragile”
of the ACI Sécurité Informatique, and from the project “Grand Large” of INRIA.