A note on the approximability of the dense subgraph problem

A.O.Stronska

The Dense Subgraph Problem is, given a graph $G$ and an integer $a$, to determine the maximum number of edges in a subgraph of $G$ induced on $a$ vertices. This optimization problem is well known to be NP-hard. We prove that finding an approximate solution with an absolute error guarantee of $a^{2-\epsilon}$ is still NP-hard for each $\epsilon>0$.

1. Визинг В.Г. Хроматический класс мультиграфа, Кибернетика, 3 (1965), 29--39. English translation available: Vizing V.G. The chromatic class of a multigraph, Cybernetics, 1:32--41 (1965).

2. Bellare M., Goldreich O., Sudan M. Free bits, PCPs, and non-approximability -- towards tight results, SIAM J.\ Computing, 27 (1998), no.3, 804--915.

3. Crescenzi P., Kann V. A compendium of NP optimization problems, On-line version available at\\ http://www.nada.kth.se/~viggo/wwwcompendium/

4. Erdos P., Spencer J. Probabilistic methods in combinatorics. Akad\'emiai Kiad\'o, Budapest (1974). Russian translation available: Эрд\"еш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976.

5. Feige U., Kortsarz G., Peleg D. The Dense $k$-Subgraph problem, Algorithmica, 29 (2001), no.3, 410--421.

6. Frieze A., Jerrum M. Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica, 18 (1997), 67--81.

7. Garey M.R., Johnson D.S. Computers and Intractability. A guide to the theory of NP-completeness, W.H.~Freeman, San Francisko (1979). A Russian translation available: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.

8. Goemans M., Williamson D. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J.\ of the ACM 42 (1995), no 6, 1115--1145.

9. Khanna S., Motwani R., Sudan M., Vazirani U. On syntactic versus computational views of approximability, SIAM J.\ Computing 28 (1999), 164--191.

10. H stad J. Some optimal inapproximability results. In: Proc.\ of the 29-th ACM Ann.\ Symp.\ on Theory of Computing, (1997), 1--10.

11. Holyer I. The NP-completeness of edge-coloring, SIAM J.\ Computing\/ 10 (1981), no.4, 718--720.

12. Ye Y.\ A. 699 approximation algorithm for MAX BISECTION. Manuscript, 1999.

	A note on the approximability of the dense subgraph problem
Author	O. V. Verbitsky. Department of Algebra and Mathematical Logic ,Faculty of Mechanics and Mathematics ,Kyiv National University, Ukraine
Abstract	The Dense Subgraph Problem is, given a graph $G$ and an integer $a$, to determine the maximum number of edges in a subgraph of $G$ induced on $a$ vertices. This optimization problem is well known to be NP-hard. We prove that finding an approximate solution with an absolute error guarantee of $a^{2-\epsilon}$ is still NP-hard for each $\epsilon>0$.
Keywords	dense subgraph problem, NP-hard problem, approximate solution
DOI	doi:10.30970/ms.22.2.198-201
Reference	1. Визинг В.Г. Хроматический класс мультиграфа, Кибернетика, 3 (1965), 29--39. English translation available: Vizing V.G. The chromatic class of a multigraph, Cybernetics, 1:32--41 (1965). 2. Bellare M., Goldreich O., Sudan M. Free bits, PCPs, and non-approximability -- towards tight results, SIAM J.\ Computing, 27 (1998), no.3, 804--915. 3. Crescenzi P., Kann V. A compendium of NP optimization problems, On-line version available at\\ http://www.nada.kth.se/~viggo/wwwcompendium/ 4. Erdos P., Spencer J. Probabilistic methods in combinatorics. Akad\'emiai Kiad\'o, Budapest (1974). Russian translation available: Эрд\"еш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976. 5. Feige U., Kortsarz G., Peleg D. The Dense $k$-Subgraph problem, Algorithmica, 29 (2001), no.3, 410--421. 6. Frieze A., Jerrum M. Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica, 18 (1997), 67--81. 7. Garey M.R., Johnson D.S. Computers and Intractability. A guide to the theory of NP-completeness, W.H.~Freeman, San Francisko (1979). A Russian translation available: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982. 8. Goemans M., Williamson D. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J.\ of the ACM 42 (1995), no 6, 1115--1145. 9. Khanna S., Motwani R., Sudan M., Vazirani U. On syntactic versus computational views of approximability, SIAM J.\ Computing 28 (1999), 164--191. 10. H stad J. Some optimal inapproximability results. In: Proc.\ of the 29-th ACM Ann.\ Symp.\ on Theory of Computing, (1997), 1--10. 11. Holyer I. The NP-completeness of edge-coloring, SIAM J.\ Computing\/ 10 (1981), no.4, 718--720. 12. Ye Y.\ A. 699 approximation algorithm for MAX BISECTION. Manuscript, 1999.
Pages	198-201
Volume	22
Issue	2
Year	2004
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html