Abstract
Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. This means that unless P=NP these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.
This work was supported by the CEE project ALCOM-IT ESPRIT LTR, project no. 20244, “Algorithms and Complexity in Information Technology”; the Italian Project “Algoritmi, Modelli di Calcolo e Strutture Informative”, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, and by TFR. Parts of this work were done when the first author was visiting the Royal Institute of Technology.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai. Recursive construction for 3-regular expanders. Proc. 28th Ann. IEEE Symp. on Foundations of Comput. Sci., 295–304, 1987.
E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoret. Comput. Sci. 147, 181–210, 1995.
S. Arora and S. Safra, Probabilistic checking of proofs; a new characterization of NP. Proc. 33rd Annual IEEE Symp. Found. Comput. Sci. IEEE Comput. Soc., 2–13, 1992.
M. Bellare, O. Goldreich, and M. Sudan, Free Bits, PCPs and nonapproximability-towards tight results, Proc. of the 36th Annual IEEE Conference on Foundations of Computer Science, 422–431, 1995.
P. Berman and T. Fujito, On approximation properties of the independent set problem for degree 3 graphs, Proc. 3rd Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 955, 449–460, Springer-Verlag, 1995.
P. Berman and M. Fürer, Approximating maximum independent set in bounded degree graphs, Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 365–371, 1994.
P. Crescenzi and V. Kann, A compendium of NP optimization problems, Technical Report SI/RR-95/02, Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza”, 1995. The list is updated continuously. The latest version is available as http://www.nada.kth.se/theory/problemlist.html.
P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan, Structure in approximation classes, Proc. 1st Ann. Int. Conf. Computing and Combinatorics, Lecture Notes in Comput. Sci. 959, Springer-Verlag, 539–548, 1995.
P. Crescenzi, R. Silvestri, and L. Trevisan, To weight or not to weight: Where is the question? Proc. 4th Israel Symp. Theory Comput. and Syst., 68–77, 1996.
M. R. Garey and D. S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, 1979.
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115–1145, 1995.
R. Greenlaw and R. Petreschi, Cubic graphs, ACM Computing Surveys 27, 471–495, 1995.
M. M. Halldorsson, Approximating the minimum maximal independence number, Inform. Process. Lett. 46, 169–172, 1993.
V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-compIete, Inform. Process. Lett. 37, 27–35, 1991.
V. Kann, On the Approximability of NP-Complete Optimization Problems, PhD Thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.
V. Kann, Polynomially bounded minimization problems that are hard to approximate, Nordic J. Computing 1 317–331, 1994.
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J. ACM 41, 960–981, 1994.
C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43, 425–440, 1991.
C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alimonti, P., Kann, V. (1997). Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds) Algorithms and Complexity. CIAC 1997. Lecture Notes in Computer Science, vol 1203. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62592-5_80
Download citation
DOI: https://doi.org/10.1007/3-540-62592-5_80
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62592-6
Online ISBN: 978-3-540-68323-0
eBook Packages: Springer Book Archive