zbMATH — the first resource for mathematics

Some APX-completeness results for cubic graphs. (English) Zbl 0939.68052
Summary: 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. Therefore, unless P=NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
[1] M. Ajtai, Recursive construction for 3-regular expanders, Proc. 28th Ann. IEEE Symp. on Foundations of Comput. Sci., 1987 pp. 295-304.
[2] Amaldi, E.; Kann, V., The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoret. comput. sci., 147, 181-210, (1995) · Zbl 0884.68093
[3] S. Arora, S. Safra, Probabilistic checking of proof: a new characterization of NP, Proc. 33rd Annual IEEE Symp. on the Foundations of Computer Science, 1992, pp. 2-13. · Zbl 0945.68516
[4] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Approximate Solution of NP-Hard Optimization Problems, Springer, Berlin, 1988, to appear. · Zbl 0937.68002
[5] M. Bellare, O. Goldreich, M. Sudan, Free Bits, PCPs and non-approximability-towards tight results, Proc. of the 36th Annual IEEE Conf. on Foundations of Computer Science, 1995, pp. 422-431. · Zbl 0938.68820
[6] P. Berman, 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 Computer Science, vol. 955, Springer, Berlin, 1995. · Zbl 0916.68109
[7] P. Berman, M. Fürer, Approximating maximum independent set in bounded degree graphs, Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 1994, pp. 365-371. · Zbl 0873.68163
[8] P. Crescenzi, 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.
[9] P. Crescenzi, V. Kann, R. Silvestri, L. Trevisan, Structure in approximation classes, Proc. 1st Ann. Int. Conf. Computing and Combinatorics, Lecture Notes in Computer Science, vol. 959, Springer, Berlin, 1995, pp. 539-548. · Zbl 0932.68137
[10] Crescenzi, P.; Panconesi, A., Completeness in approximation classes, Inform. comput., 93, 241-262, (1991) · Zbl 0734.68039
[11] P. Crescenzi, R. Silvestri, L. Trevisan, To weight or not to weight: where is the question? Proc. 4th Ann. Israel Symp. Theory Comput. and Systems, IEEE, 1996, pp. 68-77.
[12] Garey, M.R.; Johnson, D.S., Computers and intractabilitya guide to the theory of NP-completeness, (1979), W.H. Freeman and Company San Francisco
[13] Goemans, M.X.; Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,, J. ACM, 42, 1115-1145, (1995) · Zbl 0885.68088
[14] Greenlaw, R.; Petreschi, R.; graphs, Cubic graphs, ACM comput. surveys, 27, 471-495, (1995)
[15] Halldorsson, M.M., Approximating the minimum maximal independence number, Inform. process. lett., 46, 169-172, (1993) · Zbl 0778.68041
[16] M.M. Halldórsson, Approximating \(k\)-set cover and complementary graph coloring, Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 1084, Springer, Berlin, 1996, pp. 118-131.
[17] M.M. Halldórsson, K. Yoshihara, Greedy approximations of independent sets in low degree graphs, Proc. 6th Int. Symp. Algorithms and Comput., Lecture Notes in Computer Science, vol. 1004, Springer, Berlin, 1995, pp. 152-161.
[18] Kann, V., Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. process. lett., 37, 27-35, (1991) · Zbl 0711.68045
[19] V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.
[20] Kann, V., Polynomially bounded minimization problems that are hard to approximate, Nordic J. comput., 1, 317-331, (1994) · Zbl 0817.68082
[21] H. Karloff, U. Zwick, A 7/8-approximation algorithm for MAX 3SAT?, Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE, 1997, pp. 406-415.
[22] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 960-981, (1994) · Zbl 0814.68064
[23] P. Orponen, H. Mannila, On approximation preserving reduction: complete problems and robust measures, Tech. Rep. C-1987-28, Department of Computer Science, Univ. of Helsinki, 1987.
[24] Papadimitriou, C.H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. comput. systems sci., 43, 425-440, (1991) · Zbl 0765.68036
[25] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.