{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:35Z","timestamp":1771036295369,"version":"3.50.1"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,10]]},"abstract":"\n In this article, we consider\n isolated<\/jats:italic>\n cliques and\n isolated<\/jats:italic>\n dense subgraphs. For a given graph\n G<\/jats:italic>\n , a vertex subset\n S<\/jats:italic>\n of size\n k<\/jats:italic>\n (and also its induced subgraph\n G<\/jats:italic>\n (\n S<\/jats:italic>\n )) is said to be\n c<\/jats:italic>\n -isolated if\n G<\/jats:italic>\n (\n S<\/jats:italic>\n ) is connected to its outside via less than\n ck<\/jats:italic>\n edges. The number\n c<\/jats:italic>\n is sometimes called the\n isolation factor<\/jats:italic>\n . The subgraph appears more isolated if the isolation factor is smaller. The main result in this work shows that for a fixed constant\n c<\/jats:italic>\n , we can enumerate all\n c<\/jats:italic>\n -isolated maximal cliques (including a maximum one, if any) in linear time.\n <\/jats:p>\n \n In more detail, we show that, for a given graph\n G<\/jats:italic>\n of\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges, and a positive real number\n c<\/jats:italic>\n , all\n c<\/jats:italic>\n -isolated maximal cliques can be enumerated in time\n O<\/jats:italic>\n ( c\n 4<\/jats:sup>\n 2\n 2c<\/jats:sup>\n m<\/jats:italic>\n ). From this, we can see that: (1) if\n c<\/jats:italic>\n is a constant, all\n c<\/jats:italic>\n -isolated maximal cliques can be enumerated in linear time, and (2) if\n c<\/jats:italic>\n =\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ), all\n c<\/jats:italic>\n -isolated maximal cliques can be enumerated in polynomial time. Moreover, we show that these bounds are tight. That is, if\n f<\/jats:italic>\n (\n n<\/jats:italic>\n ) is an increasing function not bounded by any constant, then there is a graph of\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges for which the number of\n f<\/jats:italic>\n (\n n<\/jats:italic>\n )-isolated maximal cliques is superlinear in\n n<\/jats:italic>\n +\n m<\/jats:italic>\n . Furthermore, if\n f<\/jats:italic>\n (\n n<\/jats:italic>\n ) = \u03c9(log\n n<\/jats:italic>\n ), there is a graph of\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges for which the number of\n f<\/jats:italic>\n (\n n<\/jats:italic>\n )-isolated maximal cliques is superpolynomial in\n n<\/jats:italic>\n +\n m<\/jats:italic>\n .\n <\/jats:p>\n \n We next introduce the idea of pseudo-cliques. A\n pseudo-clique<\/jats:italic>\n having an average degree \u03b1 and a minimum degree \u03b2, denoted by\n PC<\/jats:italic>\n (\u03b1,\u03b2), is a set\n V<\/jats:italic>\n \u2032 \u2286\n V<\/jats:italic>\n such that the subgraph induced by\n V<\/jats:italic>\n \u2032 has an average degree of at least \u03b1 and a minimum degree of at least \u03b2. This article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. Especially, we show the following results, where\n k<\/jats:italic>\n is the number of vertices of the isolated pseudo-cliques: (1) For any \u03f5 > 0 there is a graph of\n n<\/jats:italic>\n vertices for which the number of 1-isolated\n PC<\/jats:italic>\n (\n k<\/jats:italic>\n - (log\n k<\/jats:italic>\n )\n 1 + \u03f5<\/jats:sup>\n ,\n k<\/jats:italic>\n \/(log\n k<\/jats:italic>\n )\n 1 + \u03f5<\/jats:sup>\n ) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all\n c<\/jats:italic>\n -isolated\n PC<\/jats:italic>\n (\n k<\/jats:italic>\n - log\n k<\/jats:italic>\n ,\n k<\/jats:italic>\n \/log\n k<\/jats:italic>\n ), for any constant\n c<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/1597036.1597044","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Enumeration of isolated cliques and pseudo-cliques"],"prefix":"10.1145","volume":"5","author":[{"given":"Hiro","family":"Ito","sequence":"first","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_4_1","volume-title":"Handbook of Combinatorial Optimization (Supplement","author":"Bomze I.","unstructured":"Bomze , I. 1999. The maximum clique problems . In Handbook of Combinatorial Optimization (Supplement Volume A). Kluwer, Dordrecht, 1-- 74 . Bomze, I. 1999. The maximum clique problems. In Handbook of Combinatorial Optimization (Supplement Volume A). Kluwer, Dordrecht, 1--74."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/276627.276652"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"He X. Zha H. Ding C. and Simon H. 2001. Web document clustering using hyperlink structures. Tech. rep. CSE-01-006 Acta Mathematica. He X. Zha H. Ding C. and Simon H. 2001. Web document clustering using hyperlink structures. Tech. rep. CSE-01-006 Acta Mathematica.","DOI":"10.2172\/815474"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_13"},{"key":"e_1_2_1_13_1","unstructured":"Johnson D. and Trick M. 1999. Cliques coloring and satisfiability: Second dimacs implementation challenge. DIMACS Series in Discrete Math. Theor. Comput. Sci. vol. 26. Johnson D. and Trick M. 1999. Cliques coloring and satisfiability: Second dimacs implementation challenge. DIMACS Series in Discrete Math. Theor. Comput. Sci. vol. 26."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 13th International Computing and Combinatorics Conference. Lecture Notes in Computer Science","volume":"4598","author":"Komusiewicz C.","unstructured":"Komusiewicz , C. , H\u00fcffner , F. , Moser , H. , and Niedermeier , R . 2007. Isolation concepts for enumerating dense subgraphs . In Proceedings of the 13th International Computing and Combinatorics Conference. Lecture Notes in Computer Science , vol. 4598 . Springer, Berlin, 140--150. Komusiewicz, C., H\u00fcffner, F., Moser, H., and Niedermeier, R. 2007. Isolation concepts for enumerating dense subgraphs. In Proceedings of the 13th International Computing and Combinatorics Conference. Lecture Notes in Computer Science, vol. 4598. Springer, Berlin, 140--150."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366818"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science","volume":"3111","author":"Makino K.","unstructured":"Makino , K. and Uno , T . 2004. New algorithms for enumerating all maximal cliques . In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science , vol. 3111 . Springer, Berlin, 260--272. Makino, K. and Uno, T. 2004. New algorithms for enumerating all maximal cliques. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 3111. Springer, Berlin, 260--272."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2nd International Conference on Web Information Systems Engineering. 301--310","author":"Reddy P. K.","unstructured":"Reddy , P. K. and Kitsuregawa , M . 2001. An approach to relate the Web communities through bipartite graphs . In Proceedings of the 2nd International Conference on Web Information Systems Engineering. 301--310 . Reddy, P. K. and Kitsuregawa, M. 2001. An approach to relate the Web communities through bipartite graphs. In Proceedings of the 2nd International Conference on Web Information Systems Engineering. 301--310."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403025"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597044","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1597036.1597044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:11Z","timestamp":1750249091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1597036.1597044"],"URL":"https:\/\/doi.org\/10.1145\/1597036.1597044","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}