An algorithmic version of the Hajnal--Szemerédi theorem

2023/07/16 by Gan, Luyining, Han, Jie, Hu, Jie · 2 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.08056

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∈ ℕ such that n∈ 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^ε for fixed ε ∈ (0,1), the problem is NP-C. 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.

Cited by

• Clique factors in random samplings of regular graphs
• A step toward Chen-Lih-Wu conjecture

Related

• A discrepancy version of the Hajnal-Szemerédi theorem
• Towards a weighted version of the Hajnal-Szemerédi Theorem
• A robust version of the multipartite Hajnal--Szemerédi theorem
• K_r-Factors in Graphs with Low Independence Number
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem