research
∙
08/11/2023
Lossy Kernelization for (Implicit) Hitting Set Problems
We re-visit the complexity of kernelization for the d-Hitting Set proble...
share
research
∙
08/06/2023
Factoring Pattern-Free Permutations into Separable ones
We show that for any permutation π there exists an integer k_π such that...
research
∙
04/07/2023
Temporalizing digraphs via linear-size balanced bi-trees
In a directed graph D on vertex set v_1,… ,v_n, a forward arc is an arc ...
research
∙
03/20/2023
Bounded twin-width graphs are polynomially χ-bounded
We show that every graph with twin-width t has chromatic number O(ω ^k_t...
research
∙
02/16/2023
Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 ⊎ C_4
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excludi...
research
∙
01/05/2023
Extremal Independent Set Reconfiguration
The independent set reconfiguration problem asks whether one can transfo...
research
∙
12/30/2022
A quasi-quadratic vertex Kernel for Cograph edge editing
We provide a O(k^2 log k) vertex kernel for cograph edge editing. This i...
research
∙
12/05/2022
(P6, triangle)-free digraphs have bounded dichromatic number
The dichromatic number of an oriented graph is the minimum size of a par...
research
∙
09/24/2022
Twin-width V: linear minors, modular counting, and matrix multiplication
We continue developing the theory around the twin-width of totally order...
research
∙
07/15/2022
First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
We characterise the classes of tournaments with tractable first-order mo...
research
∙
06/01/2022
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...
research
∙
04/26/2022
Twin-width VII: groups
Twin-width is a recently introduced graph parameter with applications in...
research
∙
04/01/2022
Twin-width VIII: delineation and win-wins
We introduce the notion of delineation. A graph class 𝒞 is said delineat...
research
∙
10/30/2021
Twin-width VI: the lens of contraction sequences
A contraction sequence of a graph consists of iteratively merging two of...
research
∙
10/28/2021
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
07/06/2021
Twin-width and polynomial kernels
We study the existence of polynomial kernels, for parameterized problems...
research
∙
02/13/2021
Twin-width and permutations
Inspired by a width invariant defined on permutations by Guillemot and M...
research
∙
02/05/2021
Twin-width IV: low complexity matrices
We establish a list of characterizations of bounded twin-width for hered...
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
∙
12/24/2019
Maximum independent sets in (pyramid, even hole)-free graphs
A hole in a graph is an induced cycle with at least 4 vertices. A graph ...
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
∙
07/10/2019
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
research
∙
03/27/2019
Convexly independent subsets of Minkowski sums of convex polygons
We show that there exist convex n-gons P and Q such that the largest con...
research
∙
03/12/2019
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
A hole in a graph is an induced cycle of length at least 4, and an antih...
research
∙
10/10/2018
Parameterized Complexity of Independent Set in H-Free Graphs
In this paper, we investigate the complexity of Maximum Independent Set ...
research
∙
03/09/2018
Edge-decomposing graphs into coprime forests
The Barat-Thomassen conjecture, recently proved in [Bensmail et al.: A p...
research
∙
03/05/2018
EPTAS for Max Clique on Disks and Unit Balls
We propose a polynomial-time algorithm which takes as input a finite set...
research
∙
02/11/2018