research
∙
08/06/2023
Factoring Pattern-Free Permutations into Separable ones
We show that for any permutation π there exists an integer k_π such that...
share
research
∙
07/20/2023
Small But Unwieldy
We show that for any natural number s, there is a constant γ and a subgr...
research
∙
05/19/2023
Stretch-width
We introduce a new parameter, called stretch-width, that we show sits st...
research
∙
02/22/2023
Cutting Barnette graphs perfectly is hard
A perfect matching cut is a perfect matching that is also a cutset, or e...
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/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
01/10/2023
Neighbourhood complexity of graphs of bounded twin-width
We give essentially tight bounds for, ν(d,k), the maximum number of dist...
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
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
For any ε > 0, we give a polynomial-time n^ε-approximation algorithm for...
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/15/2022
Twin-width can be exponential in treewidth
For any small positive real ε and integer t > 1/ε, we build a graph with...
research
∙
04/01/2022
Twin-width VIII: delineation and win-wins
We introduce the notion of delineation. A graph class 𝒞 is said delineat...
research
∙
02/25/2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
We present a fixed-parameter tractable algorithm for first-order model c...
research
∙
02/24/2022
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
In a reduction sequence of a graph, vertices are successively identified...
research
∙
12/16/2021
Deciding twin-width at most 4 is NP-complete
We show that determining if an n-vertex graph has twin-width at most 4 i...
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
∙
01/07/2021
4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3
We show, assuming the Strong Exponential Time Hypothesis, that for every...
research
∙
10/09/2020
The Complexity of Mixed-Connectivity
We investigate the parameterized complexity in a and b of determining wh...
research
∙
08/26/2020
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
We show, assuming the Strong Exponential Time Hypothesis, that for every...
research
∙
07/28/2020
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
The Cut Count technique and the rank-based approach have lead to sin...
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
∙
03/05/2020
Maximum Clique in Disk-Like Intersection Graphs
We study the complexity of Maximum Clique in intersection graphs of conv...
research
∙
01/11/2020
Grundy Coloring friends, Half-Graphs, Bicliques
The first-fit coloring is a heuristic that assigns to each vertex, arriv...
research
∙
10/04/2019
Maximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We s...
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
∙
09/04/2019
Parameterized Intractability of Even Set and Shortest Vector Problem
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
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
∙
08/25/2019
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Local search is a widely-employed strategy for finding good solutions to...
research
∙
07/18/2019
Metric Dimension Parameterized by Treewidth
A resolving set S of a graph G is a subset of its vertices such that no ...
research
∙
11/30/2018
The inverse Voronoi problem in graphs
We introduce the inverse Voronoi diagram problem in graphs: given a grap...
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/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
∙
12/24/2017
Optimality Program in Segment and String Graphs
Planar graphs are known to allow subexponential algorithms running in ti...
research
∙
12/13/2017
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
10/31/2017
Designing RNA Secondary Structures is Hard
An RNA sequence is a word over an alphabet on four elements {A,C,G,U} ca...
research
∙
10/02/2017
On the Parameterized Complexity of Red-Blue Points Separation
We study the following geometric separation problem: Given a set R of ...
research
∙
10/01/2017