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.|