Paper Title:

Turán's Theorem Through Algorithmic Lens

Published on:

14 July 2023

Primary Category:

Data Structures and Algorithms

Paper Authors:

Fedor V. Fomin,

Petr A. Golovach,

Danil Sagunov,

Kirill Simonov

•

A new compression reduces finding cliques above Turan's bound to maximum clique on 5k vertices

•

This gives an FPT algorithm for finding cliques above Turan's bound, with running time 2.49^k(n+m)

•

The paper also gives an FPT algorithm for finding large independent sets above Turan's bound in bounded average degree graphs

•

The dependence of the algorithms on parameters is shown to be tight under ETH

•

The paper links extremal graph theory and algorithms in a new way

Finding large cliques in sparse graphs

This paper develops a compression algorithm that reduces the problem of finding a clique of size l in a sparse n-vertex graph to finding a maximum clique in a graph of size about 5k. This yields an FPT algorithm for finding cliques above Turan's bound, with running time 2.49^k(n+m). The paper also gives an algorithm for finding large independent sets above Turan's bound in graphs of bounded average degree.

Bounds on induced subgraphs in triangle-free graphs

Efficiently Finding Tightly Connected Groups in Networks

Accelerating maximal clique search via graph reduction

Cliques in 5-ary Simplex Codes

Efficient algorithm for Steiner Tree based on clique-width

Linear chromatic bound for P3-union-P2-free graphs without W4

No comments yet, be the first to start the conversation...

Sign up to comment on this paper