Lower Bound for Independence Covering in C 4 -Free Graphs

Abstract

An independent set in a graph G is a set S of pairwise non-adjacent vertices in G . A family \(\mathcal {F}\) of independent sets in G is called a k - independence covering family if for every independent set I in G of size at most k , there exists an \(S \in \mathcal {F}\) such that \(I \subseteq S\) . Lokshtanov et al. (ACM Transactions on Algorithms , 2020) showed that graphs of degeneracy d admit k -independence covering families of size \(\binom{k(d+1)}{k} \cdot 2^{o(kd)} \cdot \log n\) and used this result to design efficient parameterized algorithms for a number of problems, including Stable Odd Cycle Transversal and Stable Multicut . In light of the results of Lokshtanov et al. (ACM Transactions on Algorithms, 2020) it is quite natural to ask whether even more general families of graphs admit k -independence covering families of size \(f(k)n^{O(1)}\) . Graphs that exclude a complete bipartite graph \(K_{d+1,d+1}\) with \(d+1\) vertices on both sides as a subgraph, called \(K_{d+1,d+1}\) - free graphs , are a frequently considered generalization of d -degenerate graphs. This motivates the question of whether \(K_{d,d}\) -free graphs admit k -independence covering families of size \(f(k,d)n^{O(1)}\) . Our main result is a resounding “no” to this question—specifically, we prove that even \(K_{2,2}\) -free graphs (or equivalently \(C_4\) -free graphs) do not admit k -independence covering families of size \(f(k)n^{\frac{k}{4}-\epsilon }\) .