Dense subgraph problems with output-density conditions

ABSTRACT

We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized PTAS, even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o(n) vertices.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP -hard problems, Journal of Computer and System Sciences, v.58 n.1, p.193-210, Feb. 1999 [doi>10.1006/jcss.1998.1605]
• 4: Yuichi Asahiro , Refael Hassin , Kazuo Iwama, Complexity of finding dense subgraphs, Discrete Applied Mathematics, v.121 n.1-3, p.15-26, 15 September 2002 [doi>10.1016/S0166-218X(01)00243-8]
• 5: Yuichi Asahiro , Kazuo Iwama , Hisao Tamaki , Takeshi Tokuyama, Greedily finding a dense subgraph, Journal of Algorithms, v.34 n.2, p.203-221, Feb. 2000 [doi>10.1006/jagm.1999.1062]
• 6: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 7: Czygrinow, A. 2000. Maximum dispersion problem in dense graphs. Oper. Res. Lett. 27, 5, 223--227.
• 8: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 9: Uriel Feige, Approximating Maximum Clique by Removing Subgraphs, SIAM Journal on Discrete Mathematics, v.18 n.2, p.219-225, 2005 [doi>10.1137/S089548010240415X]
• 10: Feige, U., Peleg, D., and Kortsarz, G. 2001. The dense -subgraph problem. Algorithmica 29, 3, 410--421.
• 11: G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
• 12: Dorit S. Hochbaum, Approximating clique and biclique problems, Journal of Algorithms, v.29 n.1, p.174-200, Oct. 1998 [doi>10.1006/jagm.1998.0964]
• 13: G. Kortsarz , D. Peleg, On choosing a dense subgraph, Proceedings of the Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, p.692-701, November 03-05, 1993 [doi>10.1109/SFCS.1993.366818]
• 14: Makino, K. and Uno, T. 2004. New algorithms for enumerating all maximal cliques. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science, vol. 3111. Springer, 260--272.
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceedings of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 17: Cecilia M. Procopiuc , Michael Jones , Pankaj K. Agarwal , T. M. Murali, A Monte Carlo algorithm for fast projective clustering, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564739]
• 18: Suzuki, A. and Tokuyama, T. 2005. Dense subgraph problems with output-density conditions. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC), X. Deng and D.-Z. Du, Eds. Lecture Notes in Computer Science, vol. 3827. Springer, 266--276.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
Combinatorial optimization, approximation algorithms, dense subgraph, randomized algorithms