research-article

Dense subgraph problems with output-density conditions

Authors:

Takeshi TokuyamaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 4, Issue 4

Article No.: 43, Pages 1 - 18

https://doi.org/10.1145/1383369.1383374

Published: 22 August 2008 Publication History

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]

Agrawal, R., Imielinski, T., and Swami, A. N. 1993. Mining association rules between sets of items in large database. In Proceedings of the ACM SIGMOD International Conference on Management of Data, P. Buneman and S. Jajodia, Eds. ACM Press, 207--216.

Digital Library

[2]

Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules in large databases. In Proceedings of the International Conference on Very Large Databases (VLDB), J. B. Bocca et al., Eds. Morgan Kaufmann, 487--499.

Digital Library

[3]

Arora, S., Karger, D. R., and Karpinski, M. 1999. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58, 1, 193--210.

Digital Library

[4]

Asahiro, Y., Hassin, R., and Iwama, K. 2002. Complexity of finding dense subgraphs. Discr. App. Math. 121, 1--3, 15--26.

Digital Library

[5]

Asahiro, Y., Iwama, K., Tamaki, H., and Tokuyama, T. 2000. Greedily finding a dense subgraph. J. Algor. 34, 2, 203--221.

Digital Library

[6]

Clarkson, K. L. and Shor, P. W. 1989. Application of random sampling in computational geometry, II. Discr. Comput. Geom. 4, 387--421.

Digital Library

[7]

Czygrinow, A. 2000. Maximum dispersion problem in dense graphs. Oper. Res. Lett. 27, 5, 223--227.

Digital Library

[8]

Feige, U. 2002. Relations between average case complexity and approximation complexity. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 534--543.

Digital Library

[9]

Feige, U. 2004. Approximating maximum clique by removing subgraphs. SIAM J. Discr. Math. 18, 2, 219--225.

Digital Library

[10]

Feige, U., Peleg, D., and Kortsarz, G. 2001. The dense -subgraph problem. Algorithmica 29, 3, 410--421.

Digital Library

[11]

Gallo, G., Grigoriadis, M. D., and Tarjan, R. E. 1989. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 1, 30--55.

Digital Library

[12]

Hochbaum, D. S. 1998. Approximating clique and biclique problems. J. Algor. 29, 1, 174--200.

Digital Library

[13]

Kortsarz, G. and Peleg, D. 1993. On choosing a dense subgraph (extended abstract). In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 692--701.

Digital Library

[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]

Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, New York.

Digital Library

[16]

Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999. Discovering frequent closed itemsets for association rules. In Proceedings of the International Conference on Database Theory (ICDT), C. Beeri and P. Buneman, Eds. Lecture Notes in Computer Science, vol. 1540. Springer, 398--416.

Digital Library

[17]

Procopiuc, C. M., Jones, M., Agarwal, P. K., and Murali, T. M. 2002. A Monte Carlo algorithm for fast projective clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data, M. J. Franklin et al., Eds. ACM, 418--427.

Digital Library

[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.

Digital Library

Cited By

Jones CPotechin ARajendran GXu JSaha BServedio R(2023)Sum-of-Squares Lower Bounds for Densest k-SubgraphProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585221(84-95)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585221
Angel AKoudas NSellis TMiller RKementsietsidis AVelegrakis Y(2011)Efficient diversity-aware searchProceedings of the 2011 ACM SIGMOD International Conference on Management of data10.1145/1989323.1989405(781-792)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.1145/1989323.1989405

Index Terms

Dense subgraph problems with output-density conditions
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

On choosing a dense subgraph
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

This paper concerns the problem of computing the densest k-vertex subgraph of a given graph, namely, the subgraph with the most edges, or with the highest edges-to-vertices ratio. A sequence of approximation algorithms is developed for the problem, with ...
Dense subgraph problems with output-density conditions
ISAAC'05: Proceedings of the 16th international conference on Algorithms and Computation

We consider the dense subgraph problem that extracts a subgraph with a prescribed number of vertices that has the maximum number of edges (total edge weight in the weighted case) in a given graph. We give approximation algorithms with improved ...
Proportionally dense subgraph of maximum size: Complexity and approximation
Abstract
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 4, Issue 4

August 2008

264 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1383369

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2008

Accepted: 01 April 2008

Revised: 01 April 2007

Received: 01 February 2006

Published in TALG Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
452
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jones CPotechin ARajendran GXu JSaha BServedio R(2023)Sum-of-Squares Lower Bounds for Densest k-SubgraphProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585221(84-95)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585221
Angel AKoudas NSellis TMiller RKementsietsidis AVelegrakis Y(2011)Efficient diversity-aware searchProceedings of the 2011 ACM SIGMOD International Conference on Management of data10.1145/1989323.1989405(781-792)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.1145/1989323.1989405

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents