An introduction to twin-width in graphs via the study of highly inapproximable problems
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.