Turán's Theorem Through Algorithmic Lens
share
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges t_r(n) in an n-vertex graph that does not contain a clique of size r+1. We establish an interesting link between Extremal Graph Theory and Algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size ℓ in an n-vertex graph G with m ≥ t_r(n)-k edges, where ℓ≤ r+1, to the problem of finding a maximum clique in a graph on at most 5k vertices. This also gives us an algorithm deciding in time 2.49^k·(n + m) whether G has a clique of size ℓ. As a byproduct of the new compression algorithm, we give an algorithm that in time 2^𝒪(td^2)· n^2 decides whether a graph contains an independent set of size at least n/(d+1) + t. Here d is the average vertex degree of the graph G. The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.
READ FULL TEXT