×

APX-hardness of domination problems in circle graphs. (English) Zbl 1181.68157

Summary: We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant \(\delta >0\) such that there is no \((1+\delta )\)-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+\varepsilon )\)-approximation algorithm for the problem [M. Damian-Iordache and S. V. Pemmaraju, “A \((2+\varepsilon )\)-approximation scheme for minimum domination on circle graphs”, J. Algorithms 42, No. 2, 255–276 (2002; Zbl 1002.05066)].

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms

Citations:

Zbl 1002.05066
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in: IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23; S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in: IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23 · Zbl 0977.68539
[2] Arora, S.; Safra, M., Probabilistic checking of proofs: A new characterization of NP, J. ACM, 45, 1, 70-122 (1998) · Zbl 0903.68076
[3] S.A. Cook, The complexity of theorem-proving procedures, in: Proc. 3rd Annual ACM Symp. on Theory of Computing, 1971, pp. 151-158; S.A. Cook, The complexity of theorem-proving procedures, in: Proc. 3rd Annual ACM Symp. on Theory of Computing, 1971, pp. 151-158
[4] Damian, M.; Pemmaraju, S. V., A \((2 + \epsilon)\)-approximation scheme for minimum domination on circle graphs, J. Algorithms, 42, 2, 255-276 (2002) · Zbl 1002.05066
[5] Gabor, C. P.; Supowit, K. J.; Hsu, W.-L., Recognizing circle graphs in polynomial time, J. ACM, 36, 3, 435-473 (1989) · Zbl 0825.68417
[6] Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebr. Discrete Methods, 1, 216-227 (1980) · Zbl 0499.05058
[7] Gavril, F., Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks, 3, 261-273 (1973) · Zbl 0259.05125
[8] (Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1995), PWS Publishing Company: PWS Publishing Company Boston) · Zbl 1368.68010
[9] Keil, J. M., The complexity of domination problems in circle graphs, Discrete Appl. Math., 42, 51-63 (1993) · Zbl 0786.05079
[10] Levin, L., Universal’nyie perebornyie zadachi, Problemy Peredachi Informatsii, 9, 3, 265-266 (1973), (in Russian)
[11] McKee, T. A.; McMorris, F. R., Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0945.05003
[12] Spinrad, J., Recognition of circle graphs, J. Algorithms, 16, 2, 264-282 (1994) · Zbl 0797.68130
[13] Vazirani, V., Approximation Algorithms (2003), Springer-Verlag: Springer-Verlag Berlin · Zbl 1005.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.