Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number

Abstract

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. From the main result, we propose an algorithm $\text{EIS}$ 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 $\text{EIS}$ works correctly even if the exact value of $q$ is unknown. Despite its simplicity, $\text{EIS}$ is optimal for graphs with a bounded clique number, such as, triangle-free graphs, planar graphs, bounded degenerate graphs, locally bounded expansion 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.

References in corpus (4)

• Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
• Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four
• Amortized $\tilde{O}(|V|)$-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Efficient Enumeration of Dominating Sets for Sparse Graphs

Cited by in corpus (1)

• Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size