TY - GEN

T1 - Approximation algorithms for domination search

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Thilikos, Dimitrios M.

PY - 2011

Y1 - 2011

N2 - The r-domination search game on graphs is a game-theoretical approach to the investigation of several graph and hypergraph parameters including treewidth and hypertree width. The task is to identify the minimum number of cops sufficient to catch the visible and fast robber. In r-domination search, the robber is being arrested if he resides inside a ball of radius r around some cop. In this setting, the power of the cops does not depend only on how many they are but also on the local topology of the graph around them. This is the main reason why the approximation complexity of the r-domination search game varies considerably, depending on whether r = 0 or r ≥ 1. We prove that this discrepancy is canceled when the game is played in (non-trivial) graph classes that are closed under taking of minors. We give a constant factor approximation algorithm that for every fixed r and graph H, computes the minimum number of cops required to capture the robber in the r-domination game on graphs excluding H as a minor.

AB - The r-domination search game on graphs is a game-theoretical approach to the investigation of several graph and hypergraph parameters including treewidth and hypertree width. The task is to identify the minimum number of cops sufficient to catch the visible and fast robber. In r-domination search, the robber is being arrested if he resides inside a ball of radius r around some cop. In this setting, the power of the cops does not depend only on how many they are but also on the local topology of the graph around them. This is the main reason why the approximation complexity of the r-domination search game varies considerably, depending on whether r = 0 or r ≥ 1. We prove that this discrepancy is canceled when the game is played in (non-trivial) graph classes that are closed under taking of minors. We give a constant factor approximation algorithm that for every fixed r and graph H, computes the minimum number of cops required to capture the robber in the r-domination game on graphs excluding H as a minor.

KW - approximation algorithms

KW - Domination search

KW - graph minors

UR - http://www.scopus.com/inward/record.url?scp=79551538621&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79551538621&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18318-8_12

DO - 10.1007/978-3-642-18318-8_12

M3 - Conference contribution

AN - SCOPUS:79551538621

SN - 9783642183171

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 130

EP - 141

BT - Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers

T2 - 8th International Workshop on Approximation and Online Algorithms, WAOA 2010

Y2 - 9 September 2010 through 10 September 2010

ER -