Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
share
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 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 EIS works correctly even if the exact value of q is unknown. Despite its simplicity, 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.
READ FULL TEXT