Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Monotonicity and connectivity for width parameters

The notion of an expansion is a useful framework for defining several known width parameters on graphs. We survey the relation of such parameters with search and conquer games. The goal in these games is to systematically maneuver searches in order to capture a fugitive who flees around the graph or alternatively to organize a gradual occupation of the graph while minimizing specific cost functions. An important question is the so called "monotonicity question": does it cost more to search/conquer a graph if we do not allow the fugitive to visit again "clean" locations? Another question is the "connectivity question": does it cost more to search/conquer a graph if we demand "clean" positions to induce a connected part of the graph? We use expansions to settle the monotonicity and the connectivity questions and we comment related recent results and open problems on their study.