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 -