Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
share
We show that a graph with n vertices and vertex cover of size k has at most 4^k + n potential maximal cliques. We also show that for each positive integer k, there exists a graph with vertex cover of size k, O(k^2) vertices, and Ω(4^k) potential maximal cliques. Our results extend the results of Fomin, Liedloff, Montealegre, and Todinca [Algorithmica, 80(4):1146–1169, 2018], who proved an upper bound of poly(n) 4^k, but left the lower bound as an open problem.
READ FULL TEXT