Paper Image

Finding large cliques in sparse graphs

Published on:

14 July 2023

Primary Category:

Data Structures and Algorithms

Paper Authors:

Fedor V. Fomin,

Petr A. Golovach,

Danil Sagunov,

Kirill Simonov

Bullets

Key Details

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

AI generated summary

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.

Answers from this paper

Comments

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

Sign up to comment on this paper

Sign Up