
Twinwidth and polynomial kernels
We study the existence of polynomial kernels, for parameterized problems...
read it

Twinwidth and permutations
Inspired by a width invariant defined on permutations by Guillemot and M...
read it

Twinwidth IV: low complexity matrices
We establish a list of characterizations of bounded twinwidth for hered...
read it

4 vs 7 sparse undirected unweighted Diameter is SETHhard at time n^4/3
We show, assuming the Strong Exponential Time Hypothesis, that for every...
read it

The Complexity of MixedConnectivity
We investigate the parameterized complexity in a and b of determining wh...
read it

Inapproximability of Diameter in superlinear time: Beyond the 5/3 ratio
We show, assuming the Strong Exponential Time Hypothesis, that for every...
read it

Close relatives of Feedback Vertex Set without singleexponential algorithms parameterized by treewidth
The Cut Count technique and the rankbased approach have lead to sin...
read it

Twinwidth III: Max Independent Set and Coloring
We recently introduced the graph invariant twinwidth, and showed that f...
read it

Twinwidth II: small classes
The twinwidth of a graph G is the minimum integer d such that G has a d...
read it

Twinwidth I: tractable FO model checking
Inspired by a width invariant defined on permutations by Guillemot and M...
read it

An algorithmic weakening of the ErdősHajnal conjecture
We study the approximability of the Maximum Independent Set (MIS) proble...
read it

Maximum Clique in DiskLike Intersection Graphs
We study the complexity of Maximum Clique in intersection graphs of conv...
read it

Grundy Coloring friends, HalfGraphs, Bicliques
The firstfit coloring is a heuristic that assigns to each vertex, arriv...
read it

Maximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We s...
read it

When Maximum Stable Set can be solved in FPT time
Maximum Independent Set (MIS for short) is in general graphs the paradig...
read it

Parameterized Intractability of Even Set and Shortest Vector Problem
The kEven Set problem is a parameterized variant of the Minimum Distanc...
read it

Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Given a hypergraph H, the Minimum Connectivity Inference problem asks fo...
read it

FineGrained Complexity of kOPT in BoundedDegree Graphs for Solving TSP
Local search is a widelyemployed strategy for finding good solutions to...
read it

Metric Dimension Parameterized by Treewidth
A resolving set S of a graph G is a subset of its vertices such that no ...
read it

The inverse Voronoi problem in graphs
We introduce the inverse Voronoi diagram problem in graphs: given a grap...
read it

Parameterized Complexity of Independent Set in HFree Graphs
In this paper, we investigate the complexity of Maximum Independent Set ...
read it

EPTAS for Max Clique on Disks and Unit Balls
We propose a polynomialtime algorithm which takes as input a finite set...
read it

Optimality Program in Segment and String Graphs
Planar graphs are known to allow subexponential algorithms running in ti...
read it

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
read it

Designing RNA Secondary Structures is Hard
An RNA sequence is a word over an alphabet on four elements {A,C,G,U} ca...
read it

On the Parameterized Complexity of RedBlue Points Separation
We study the following geometric separation problem: Given a set R of ...
read it

Orthogonal Terrain Guarding is NPcomplete
A terrain is an xmonotone polygonal curve, i.e., successive vertices ha...
read it
Édouard Bonnet
is this you? claim profile