ALLSAT compressed with wildcards: All, or all maximum independent sets

2009/01/28 by Marcel Wild, Wild, Marcel
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #Limits and Structures in Graph Theory #Mathematical Software (cs.MS)

paper · pdf · doi:10.48550/arxiv.0901.4417

openalex publication_date 2009/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An odd cycle cover is a vertex set whose removal makes a graph bipartite. We show that if a k-element odd cycle cover of a graph with w vertices is known then all N maximum anticliques (= independent sets) can be generated in time O(2^k w³ + N w²)). Generating \it all N' anticliques (maximum or not) is easier and works for arbitrary graphs in time O(N'w²). In fact the use of wildcards allows to compactly generate the anticliques in clusters.

Citations

• Fibonacci Numbers of Graphs

Related

• Induced odd cycle packing number, independent sets, and chromatic number
• ALLSAT compressed with wildcards: Frequent Set Mining
• Compression with wildcards: All induced metric subgraphs
• Mining Maximal Induced Bicliques using Odd Cycle Transversals
• Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes