On the algorithmic aspects of Turán's Theorem

Turán's Theorem gives an upper bound on the number of edges of n-node, K_r-free graphs, or equivalently it can be restated as that every n-node, m-edge graph has an independent set of size n^2/(n+2m). We illustrate how to apply Turán's Theorem to algorithmic problems in several ways. The complexity of dictionary operations, insertion for example, in external memory is well studied. However, the complexity of a batch of n operations is less known, and is seldom as easy as summing up the complexity of individual operations. We obtain lower bounds for batched predecessors by showing the necessity of fetching a set of information that preserves some "independence", where Turán's Theorem applies. We also prove lower bounds for batched deletions in cross-referenced dictionaries based on the existence of an adversarial input that forbids some patterns, where Turán's Theorem again applies. In addition, we present an interesting class of problems that are NP-hard to approximate. Turán’s theorem is useful in the proof that a large class of problems that can be defined in a simple framework are all NP-hard to approximate.Ph.D.Includes bibliographical referencesby Meng-Tsung Tsa