APX-Hardness of Domination Problems in Circle Graphs.

We show that the problem of ¯nding a minimum dominating set in a circle graph is APX- hard: there is a constant ± > 0 such that there is no (1 + ±)-approximation algorithm for the minimum dominating set problem on circle graphs unless P = NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2 + ")-approximation algorithm for the problem (Journal of Algorithms, 42(2), 255-276, 2002).

Main Author: Damian, Mirela.
Other Authors: Pemmaraju, Sriram. V.
Format: Villanova Faculty Authorship
Language: English
Published: 2006
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175641