research
∙
07/15/2022
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
For any ε > 0, we give a polynomial-time n^ε-approximation algorithm for...
share
research
∙
04/12/2022
1-Extendability of independent sets
In the 70s, Berge introduced 1-extendable graphs (also called B-graphs),...
research
∙
07/06/2021
Twin-width and polynomial kernels
We study the existence of polynomial kernels, for parameterized problems...
research
∙
07/28/2020
Twin-width III: Max Independent Set and Coloring
We recently introduced the graph invariant twin-width, and showed that f...
research
∙
06/17/2020
Twin-width II: small classes
The twin-width of a graph G is the minimum integer d such that G has a d...
research
∙
04/30/2020
Twin-width I: tractable FO model checking
Inspired by a width invariant defined on permutations by Guillemot and M...
research
∙
04/25/2020
An algorithmic weakening of the Erdős-Hajnal conjecture
We study the approximability of the Maximum Independent Set (MIS) proble...
research
∙
09/18/2019
When Maximum Stable Set can be solved in FPT time
Maximum Independent Set (MIS for short) is in general graphs the paradig...
research
∙
08/26/2019
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Given a hypergraph H, the Minimum Connectivity Inference problem asks fo...
research
∙
10/10/2018