Approximation hardness of dominating set problems

Miroslav Chlebik, Janka Chlebikova

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


We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.
Original languageEnglish
Title of host publicationAlgorithms – ESA 2004
Subtitle of host publication12th annual European symposium, Bergen, Norway, September 14-17, 2004. proceedings
EditorsSusanne Albers, Tomasz Radzik
Place of PublicationBerlin
ISBN (Electronic)9783540301400
ISBN (Print)9783540230250
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Approximation hardness of dominating set problems'. Together they form a unique fingerprint.

Cite this