/Exposé en anglais/Talk in english/

Twin-width is a graph invariant recently introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20].
The core result of their paper states that, on classes of bounded twin-width, deciding any problem expressible by a first-order logic formula φ is FPT with respects to |φ|.
Bounded twin-width classes are very diverse, and plenty of decision problems such as k-Independent Set, k-Dominating Set and k-Vertex Cover can be expressed in first order, yielding their fixed-parameter tractability on these classes.

In this talk, we investigate the existence of polynomial kernels for k-Vertex Cover and k-Dominating Set on classes of bounded twin-width.
In these classes, we start by showing a (sub)quadratic kernel k-Vertex Cover.
After introducing the background required for kernel lower bounds, we present our main result, that k-Dominating Set admits no polynomial kernel on classes of twin-width at most four.

Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant [Algorithmica, https://arxiv.org/abs/2107.02882 ]

[Amadeus Reinald] (LIRMM )

https://www.lirmm.fr/~areinald/about/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .