A parameterized algorithm for $K_r$-factors in graphs of high minimum degree

Abstract

A $K_r$-factor of a graph $G$ is a collection of vertex-disjoint $r$-cliques covering $V(G)$. We prove the following algorithmic version of the classical Hajnal--Szemerédi Theorem in graph theory, when $r$ is considered as a constant. Given $r,c,n\in \mathbb{N}$ such that $n\in r\mathbb{N}$, let $G$ be an $n$-vertex graph with minimum degree at least $(1-1/r)n-c$. Then there is an algorithm with running time $2^{c^{O(1)}}{n}^{O(1)}$ that outputs either a $K_r$-factor of $G$ or a certificate showing that none exists, namely, this problem is fixed-parameter tractable in $c$. On the other hand, it is known that if $c=n^{\epsilon }$ for fixed $\epsilon \in (0,1)$, the problem is \texttt{NP-C}. By taking the complement, our result yields a similar result on the equitable $\hat{I}”$-colorings of graphs of maximum degree $\hat{I}”+c$, for $\hat{I}”\in [n/r,n/(r-1)]$. We indeed establish characterization theorems for this problem, showing that the existence of a $K_r$-factor is equivalent to the existence of certain class of $K_r$-tilings of size $o(n)$, whose existence can be searched by the color-coding technique developed by Alon--Yuster--Zwick.

36 pages