Isolation concepts for efficiently enumerating dense subgraphs. (English) Zbl 1171.68030
Summary: In an undirected graph \(G=(V,E)\), a set of \(k\) vertices is called \(c\)-isolated if it has less than \(c\cdot k\) outgoing edges. H. Ito and K. Iwama [“Enumeration of isolated cliques and pseudo-cliques”, ACM Trans. Algorithms (in press)] gave an algorithm to enumerate all \(c\)-isolated maximal cliques in \(O(4^c \cdot c^{4}\cdot |E|\)) time. We extend this to enumerating all maximal \(c\)-isolated cliques (which are a superset) and improve the running time bound to \(O(2.89^c \cdot c^{2}\cdot |E|\)), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to \(s\)-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the \(s\)-plex is the parameter and a fixed-parameter algorithm for enumerating isolated \(s\)-plexes when the parameter describes the degree of isolation.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C30 | Enumeration in graph theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
NP-hard problem; parameterized complexity; fixed-parameter tractability; exact algorithm; clique; \(s\)-plexReferences:
| [1] | B. Balasundaram, S. Butenko, I.V. Hicks, S. Sachdeva, Clique relaxations in social network analysis: The maximum \(k\); B. Balasundaram, S. Butenko, I.V. Hicks, S. Sachdeva, Clique relaxations in social network analysis: The maximum \(k\) · Zbl 1218.90228 |
| [2] | Balasundaram, B.; Butenko, S.; Trukhanovzu, S., Novel approaches for analyzing biological networks, Journal of Combinatorial Optimization, 10, 1, 23-39 (2005) · Zbl 1080.90010 |
| [3] | Butenko, S.; Wilhelm, W. E., Clique-detection models in computational biochemistry and genomics, European Journal of Operational Research, 173, 1, 1-17 (2006) · Zbl 1125.92025 |
| [4] | Chesler, E. J.; Lu, L.; Shou, S.; Qu, Y.; Gu, J.; Wang, J.; Hsu, H. C.; Mountz, J. D.; Baldwin, N. E.; Langston, M. A.; Threadgill, D. W.; Manly, K. F.; Williams, R. W., Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system function, Nature Genetics, 37, 3, 233-242 (2005) |
| [5] | Damaschke, P., Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theoretical Computer Science, 351, 3, 337-350 (2006) · Zbl 1087.68067 |
| [6] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [7] | Fellows, M. R.; Guo, J.; Moser, H.; Niedermeier, R., A generalization of Nemhauser and Trotter’s local optimization theorem, (Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS’09, Dagstuhl Seminar Proceedings, pages 409-420. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS’09, Dagstuhl Seminar Proceedings, pages 409-420, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI) (2009), Schloss Dagstuhl: Schloss Dagstuhl Germany) · Zbl 1235.68081 |
| [8] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [9] | Fomin, F. V.; Grandoni, F.; Kratsch, D., Measure and conquer: A simple \(O(2^{0.288 n})\) independent set algorithm, (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’06 (2006), ACM Press), 18-25 · Zbl 1192.68960 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [11] | Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), Acta Mathematica, 182, 1, 105-142 (1999) · Zbl 0989.68060 |
| [12] | Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Enumerating isolated cliques in synthetic and financial networks, (Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications. Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08. Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications. Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08, LNCS, vol. 5165 (2008), Springer), 405-416 · Zbl 1168.05367 |
| [13] | Hüffner, F.; Niedermeier, R.; Wernicke, S., Fixed-parameter algorithms for graph-modeled data clustering, (Butenko, S.; Chaovalitwongse, W. A.; Pardalos, P. M., Clustering Challenges in Biological Networks (2009), World Scientific) |
| [14] | H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press); H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press) · Zbl 1298.05250 |
| [15] | Ito, H.; Iwama, K.; Osumi, T., Linear-time enumeration of isolated cliques, (Proceedings of the 13th European Symposium on Algorithms. Proceedings of the 13th European Symposium on Algorithms, ESA ’05. Proceedings of the 13th European Symposium on Algorithms. Proceedings of the 13th European Symposium on Algorithms, ESA ’05, LNCS, vol. 3669 (2005), Springer), 119-130 · Zbl 1162.68497 |
| [16] | C. Komusiewicz, Various isolation concepts for the enumeration of dense subgraphs, Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, 2007; C. Komusiewicz, Various isolation concepts for the enumeration of dense subgraphs, Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, 2007 |
| [17] | Komusiewicz, C.; Hüffner, F.; Moser, H.; Niedermeier, R., Isolation concepts for enumerating dense subgraphs, (Proceedings of the 13th International Computing and Combinatorics Conference. Proceedings of the 13th International Computing and Combinatorics Conference, COCOON’07. Proceedings of the 13th International Computing and Combinatorics Conference. Proceedings of the 13th International Computing and Combinatorics Conference, COCOON’07, LNCS, vol. 4598 (2007), Springer), 140-150 · Zbl 1206.68237 |
| [18] | Kosub, S., Local density, (Brandes, U.; Erlebach, T., Network Analysis: Methodological Foundations. Network Analysis: Methodological Foundations, LNCS, vol. 3418 (2005), Springer), 112-142, (Chapter 6) · Zbl 1118.68332 |
| [19] | Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, Journal of Computer and System Sciences, 20, 2, 219-230 (1980) · Zbl 0436.68029 |
| [20] | Moser, H.; Niedermeier, R.; Sorge, M., Algorithms and experiments for clique relaxations—finding maximum \(s\)-plexe, (Proceedings of the 8th International Symposium on Experimental Algorithms. Proceedings of the 8th International Symposium on Experimental Algorithms, SEA’09. Proceedings of the 8th International Symposium on Experimental Algorithms. Proceedings of the 8th International Symposium on Experimental Algorithms, SEA’09, LNCS, vol. 5526 (2009), Springer), 233-244 |
| [21] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [22] | Nishimura, N.; Ragde, P.; Thilikos, D. M., Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Discrete Applied Mathematics, 152, 1-3, 229-245 (2005) · Zbl 1080.05093 |
| [23] | Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 7043, 814-818 (2005) |
| [24] | Robson, J. M., Algorithms for maximum independent sets, Journal of Algorithms, 7, 3, 425-440 (1986) · Zbl 0637.68080 |
| [25] | Seidman, S. B.; Foster, B. L., A graph-theoretic generalization of the clique concept, Journal of Mathematical Sociology, 6, 1, 139-154 (1978) · Zbl 0386.92015 |
| [26] | Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, 363, 1, 28-42 (2006) · Zbl 1153.68398 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
