Graph Searching and Graph Decompositions

Description

Graph searching is a game where a team of mobile agents must catch a fugitive hidden in a network (modelled by a graph). Equivalently, graph searching may be defined in terms of clearing a contaminated network. Besides of its practical interests, graph searching has been widely studied for its relationship with important graph parameters, in particular pathwidth and treewidth. Many versions of graph searching problems have been considered. They all look for a strategy that allows to catch the fugitive using the minimum number of agents. Variants of graph searching differ on various parameters. We first give a brief survey of the numerous research directions in this field. Then, we focus on the relationship between search games and graph decompositions (path- and tree-decompositions). Namely, search games provide a very interesting algorithmic interpretation of the pathwidth and the treewidth of graphs. we explain the equivalence between theses games and graph decompositions through an important property of these two search games: the monotonicity. This point of view allowed us to obtain new duality results generalyzing those obtained by Robertson and Seymour in the Graph Minors Theory.

Abstract

International audience

Additional details