Covering all edges of a graph by a minimum number of cliques is a well known NP -hard problem. For the parameter \(k\) being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with \(n\) vertices, edge probability \(p\), and clique covers of size \(k\). We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) 17 and show that with high probability they reduce the graph completely if \(p\) is bounded away from 1 and \(k < c log n\) for some constant \(c > 0\) . This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.