Approximation algorithms for domination search

Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
Number of pages12
StatePublished - 2011
Event8th International Workshop on Approximation and Online Algorithms, WAOA 2010 - Liverpool, United Kingdom
Duration: Sep 9 2010Sep 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6534 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Country/TerritoryUnited Kingdom


  • approximation algorithms
  • Domination search
  • graph minors

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximation algorithms for domination search'. Together they form a unique fingerprint.

Cite this