An introduction to twin-width in graphs via the study of highly inapproximable problems

-- Pierre Bergé (ISIMA, Université Clermont Auvergne)

Time: 14:00 -- Location: LRI, 445

summary: The goal of this seminar is to introduce the graph parameter "twin-width", defined by Bonnet et al. in 2020. The collection of graphs with bounded twin-width generalizes many well-known families of graphs : planar, bounded treewidth and cliquewidth, unit interval,... The first motivation behind this parameter was that FO-expressible NP-hard problems can be solved on bounded twin-width graphs in polynomial time.
We focus in this talk on a new application of twin-width. We prove that several highly inapproximable problems - we will mostly focus on Max Independent Set - admit, for all c > 0, a n^c approximation in polynomial time on bounded twin-width graphs, which is very unlikely in general graphs. The algorithm is based upon the notion of versatile twin-width.

Category: seminars
Tags: Team seminar networks