SCIENTIFIC PROGRAM

Title: Duality Results for Partition Functions

Speaker: Stéphan Thomassé

Abstract: This talk will survey the work initated in the first GRASTA with Omid Amini, Frederic Mazoit and Nicolas Nisse. We introduced the notion of partition submodular functions, a framework from which can be derived the known dual notions of the differents width parameters. If time permits an LP-formulation of these results will be discussed.

_____________________________________________________________________________

Title: Graph Searching variants related to Visibility, Agility, and Speed

Speaker: Dimitrios M. Thilikos

Abstract:

Graph searching problems are usually described as a game played in a graph between a set of cops and an escaping robber. Variants of the game are generated by restricting the abilities of the robbber and are related to several known parameters in graph theory. Each variant corresponds to a searching number parameter that is the minimum number of cops for which a wining strategy exists. In this paper, we study the case where the robber is lazy (moves only when a move threatens his position) and visible (the capture strategy can take into account his current position). We give a min-max characterization of the corresponding parameter. An immediate corollary of our theorem is that the searching number for a lazy and visible robber can be computed in polynomial time. This makes a contrast to the fact that all other versions of the game (visible/agile, invisible/lazy and invisible/agile robber) correspond to {\sf NP}-hard parameters. All of our results are stated and proved for the more general setting where the robber's speed (i.e. how far he can go after a threatening move) can be unbounded or bounded but some constant.

Joint work with: David Richerby

_____________________________________________________________________________

Title: On tractability of Cops and Robbers game

Speaker: Peter Golovach

Abstract:

The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question. We prove that computing the minimum number of cops that can catch a robber on a given graph is NP-hard. Also we show that the parameterized version of the problem is W[2]-hard. Our proof can be extended for to the variant of the game where the robber can move $s$ times faster than cops. We also provide a number of algorithmic and complexity results on classes of chordal graphs and on graphs of bounded cliquewidth. For example, we show that when the velocity of the robber is twice cop's velocity, the problem is NP-hard on split graphs, while it is polynomial time solvable on split graphs when players posses the same speed. Finally, we establish that on graphs of bounded cliquewidth (this class of graphs, for example, contain graphs of bounded treewidth), the problem is solvable in polynomial time in the case the robber's speed is at most twice the speed of cops.

Joint work with: F. V. Fomin  and J. Kratochvil

_____________________________________________________________________________

Title: Distributed graph searching

Speaker: Nicolas Nisse

Abstract:

In distributed graph searching, the searchers are modeled by automata with logaritmic size memory. They must compute their own search strategy for clearing the network in which they are currently running. This distributed computation must not require knowing the topology of the network in advance, and the searchers must act in absence of any global synchronisation mechanism. In this talk, we present a short literature survey that answers the following general questions. Is it possible to design a distributed algorithm that allows to clear any graph with the optimal (in centralized settings) number of searchers? What happens if the distributed strategy is constrained to be monotone? Can we help the searchers by giving them some information about the graph (size, topology...)?

_____________________________________________________________________________

Title: Arc Searching Digraphs Without Jumping

Speaker: Boting Yang

Abstract:

The arc-searching problem is a natural extension of the edge searching problem, which is to determine the minimum number of searchers (search number) needed to capture an invisible fast intruder in a graph. We examine several models for the internal arc-searching problem, in which the searchers may not ``jump'' from a vertex to a non-adjacent vertex. We prove the monotonicity of these models. We explore some elementary results and characterize directed graphs  with small search number for the various models.

Joint work with: Brian Alspach, Danny Dyer and Denis Hanson

___________________________________________________________________