Near-Optimal Algorithms for Maximal Clique Enumeration in Structurally Sparse Graphs
We study the exact enumeration of maximal cliques in graph classes defined by excluded clique minors and excluded clique immersions. For n-vertex K_t-minor-free graphs, we give an algorithm that lists all maximal cliques in n * 4^(2t/5+o(t)) time, significantly improving the previous n * 2^O(t log log t) bound of Eppstein, Löffler, and Strash. For n-vertex K_t-immersion-free graphs, we establish the first exact enumeration algorithm parameterized by immersion number, achieving a running time of n * 3^(t/3+o(t)). While both algorithms employ a common degeneracy-based root-assignment scheme,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02614
curl -X POST /api/v1/records/arxiv/2608.02614/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02614/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'