×

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number. (English) Zbl 1507.05091

Summary: In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no fine-grained analysis has been given for the non-maximal variant. As the main result, we propose an enumeration algorithm for the non-maximal variant that runs in \(O ( q )\) amortized time and linear space, where \(q\) is the clique number, i.e., the maximum size of a clique in an input graph. Note that the proposed algorithm works correctly even if the exact value of \(q\) is unknown. It is optimal for graphs with a bounded clique number, such as, triangle-free graphs, bipartite graphs, planar graphs, bounded degenerate graphs, nowhere dense graphs, and \(F\)-free graphs for any fixed graph \(F\), where a \(F\)-free graph is a graph that has no copy of \(F\) as a subgraph. Furthermore, with a slight modification of our proposed algorithm, we can enumerate independent sets with the size at most \(k\) in the same time and space complexity. This problem is a generalization of the original problem since this is equal to the original problem if \(k = n\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C30 Enumeration in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 65, 1, 21-46 (1996) · Zbl 0854.68070
[2] Beigel, R., Finding maximum independent sets in sparse and general graphs, (Proc. SODA 1999 (1999)), 856-857 · Zbl 0938.68073
[3] Birmelé, E.; Ferreira, R. A.; Grossi, R.; Marino, A.; Pisanti, N.; Rizzi, R.; Sacomoto, G., Optimal listing of cycles and st-paths in undirected graphs, (Proc. SODA 2013 (2013)), 1884-1896 · Zbl 1423.68329
[4] Bonamy, M.; Defrain, O.; Heinrich, M.; Raymond, J.-F., Enumerating minimal dominating sets in triangle-free graphs, (Proc. STACS 2019. Proc. STACS 2019, LIPIcs, vol. 126 (2019)), Article 16 pp. · Zbl 07559125
[5] Cohen, S.; Kimelfeld, B.; Sagiv, Y., Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, J. Comput. Syst. Sci., 74, 7, 1147-1159 (2008) · Zbl 1152.68040
[6] Conte, A.; Grossi, R.; Marino, A.; Uno, T.; Versari, L., Listing maximal independent sets with minimal space and bounded delay, (Proc. SPIRE 2017. Proc. SPIRE 2017, LNCS, vol. 10508 (2017)), 144-160 · Zbl 1454.68097
[7] Conte, A.; Grossi, R.; Marino, A.; Versari, L., Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques, (Proc. ICALP 2016. Proc. ICALP 2016, LIPIcs, vol. 55 (2016)), Article 148 pp. · Zbl 1388.68218
[8] Conte, A.; Grossi, R.; Marino, A.; Versari, L., Listing maximal subgraphs satisfying strongly accessible properties, SIAM J. Discrete Math., 33, 2, 587-613 (2019) · Zbl 1409.05108
[9] Conte, A.; Uno, T., New polynomial delay bounds for maximal subgraph enumeration by proximity search, (Proc. STOC 2019 (2019)), 1179-1190 · Zbl 1433.68288
[10] Eppstein, D., Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl., 7, 2, 131-140 (2003) · Zbl 1027.05092
[11] Ferreira, R. A.; Grossi, R.; Rizzi, R.; Sacomoto, G.; Sagot, M., Amortized \(\widetilde{O}(| V |)\)-delay algorithm for listing chordless cycles in undirected graphs, (Proc. ESA 2014. Proc. ESA 2014, LNCS, vol. 8737 (2014)), 418-429 · Zbl 1423.68571
[12] Grohe, M.; Kreutzer, S.; Siebertz, S., Characterisations of nowhere dense graphs (invited talk), (Proc. FSTTCS 2013. Proc. FSTTCS 2013, LIPIcs, vol. 24 (2013)), 21-40 · Zbl 1359.05102
[13] Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H., On generating all maximal independent sets, Inf. Process. Lett., 27, 3, 119-123 (1988) · Zbl 0654.68086
[14] Kashiwabara, T.; Masuda, S.; Nakajima, K.; Fujisawa, T., Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph, J. Algorithms, 13, 1, 161-174 (1992) · Zbl 0767.68082
[15] Kurita, K.; Wasa, K.; Arimura, H.; Uno, T., Efficient enumeration of dominating sets for sparse graphs, (Proc. ISAAC 2018. Proc. ISAAC 2018, LIPIcs, vol. 123 (2018)), Article 8 pp.
[16] Kurita, K.; Wasa, K.; Uno, T.; Arimura, H., Efficient enumeration of induced matchings in a graph without cycles with length four, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 101, 9, 1383-1391 (2018)
[17] Leung, J. Y., Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs, J. Algorithms, 5, 1, 22-35 (1984) · Zbl 0544.05036
[18] Lick, D. R.; White, A. T., k-degenerate graphs, Can. J. Math., 22, 1082-1096 (1970) · Zbl 0202.23502
[19] Makino, K.; Uno, T., New algorithms for enumerating all maximal cliques, (Proc. SWAT 2004. Proc. SWAT 2004, LNCS, vol. 3111 (2004)), 260-272 · Zbl 1095.68626
[20] Manoussakis, G., A new decomposition technique for maximal clique enumeration for sparse graphs, Theor. Comput. Sci., 770, 25-33 (2019) · Zbl 1421.68138
[21] Matula, D. W.; Beck, L. L., Smallest-last ordering and clustering and graph coloring algorithms, J. ACM, 30, 3, 417-427 (1983) · Zbl 0628.68054
[22] Minty, G. J., On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B, 28, 3, 284-304 (1980) · Zbl 0434.05043
[23] Nešetřil, J.; De Mendez, P. O., Sparsity: Graphs, Structures, and Algorithms, vol. 28 (2012), Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 1268.05002
[24] Okamoto, Y.; Uno, T.; Uehara, R., Counting the number of independent sets in chordal graphs, J. Discret. Algorithms, 6, 2, 229-242 (2008) · Zbl 1146.05029
[25] Shioura, A.; Tamura, A.; Uno, T., An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM J. Comput., 26, 3, 678-692 (1997) · Zbl 0870.05066
[26] Tarjan, R. E.; Read, R. C., Bounds on backtrack algorithms for listing cycles, paths and spanning trees, Networks, 5, 237-252 (1975) · Zbl 0316.05125
[27] Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for generating all maximal cliques and computational experiments, Theor. Comput. Sci., 363, 1, 28-42 (2006) · Zbl 1153.68398
[28] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 3, 505-517 (1977) · Zbl 0364.05027
[29] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941), (in Hungarian)
[30] Uno, T., Constant time enumeration by amortization, (Proc. WADS 2015. Proc. WADS 2015, LNCS, vol. 9214 (2015)), 593-605 · Zbl 1451.68361
[31] Wasa, K.; Arimura, H.; Uno, T., Efficient enumeration of induced subtrees in a k-degenerate graph, (Proc. ISAAC 2014. Proc. ISAAC 2014, LNCS, vol. 8889 (2014)), 94-102 · Zbl 1435.05109
[32] Wasa, K.; Uno, T., Efficient enumeration of bipartite subgraphs in graphs, (Proc. COCOON 2018. Proc. COCOON 2018, LNCS, vol. 10976 (2018)), 454-466 · Zbl 1512.05200
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.