research
∙
09/14/2023
Dynamic programming on bipartite tree decompositions
We revisit a graph width parameter that we dub bipartite treewidth, alon...
share
research
∙
07/13/2023
Redicolouring digraphs: directed treewidth and cycle-degeneracy
Given a digraph D=(V,A) on n vertices and a vertex v∈ V, the cycle-degre...
research
∙
06/28/2023
New Menger-like dualities in digraphs and applications to half-integral linkages
We present new min-max relations in digraphs between the number of paths...
research
∙
10/05/2022
Faster parameterized algorithms for modification problems to minor-closed classes
Let G be a minor-closed graph class and let G be an n-vertex graph. We s...
research
∙
02/07/2022
Reducing the Vertex Cover Number via Edge Contractions
The CONTRACTION(vc) problem takes as input a graph G on n vertices and t...
research
∙
11/04/2021
A Compound Logic for Modification Problems: Big Kingdoms Fall from Within
We introduce a novel model-theoretic framework inspired from graph modif...
research
∙
05/04/2021
FPT algorithms for packing k-safe spanning rooted sub(di)graphs
We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput...
research
∙
03/11/2021
Hitting minors on bounded treewidth graphs. III. Lower bounds
For a finite collection of graphs F, the F-M-DELETION problem consists i...
research
∙
03/11/2021
Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
For a finite collection of graphs F, the F-M-DELETION (resp. F-TM-DELETI...
research
∙
03/01/2021
k-apices of minor-closed graph classes. I. Bounding the obstructions
Let G be a minor-closed graph class. We say that a graph G is a k-apex o...
research
∙
02/12/2021
A more accurate view of the Flat Wall Theorem
We introduce a supporting combinatorial framework for the Flat Wall Theo...
research
∙
02/05/2021
Parameterized complexity of computing maximum minimal blocking and hitting sets
A blocking set in a graph G is a subset of vertices that intersects ever...
research
∙
02/04/2021
Kernelization of Maximum Minimal Vertex Cover
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph...
research
∙
07/15/2020
Adapting the Directed Grid Theorem into an FPT Algorithm
The Grid Theorem of Robertson and Seymour [JCTB, 1986], is one of the mo...
research
∙
07/10/2020
Target set selection with maximum activation time
A target set selection model is a graph G with a threshold function τ:V→...
research
∙
05/20/2020
A Unifying Model for Locally Constrained Spanning Tree Problems
Given a graph G and a digraph D whose vertices are the edges of G, we in...
research
∙
05/04/2020
Reducing graph transversals via edge contractions
For a graph parameter π, the Contraction(π) problem consists in, given a...
research
∙
04/27/2020
Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
We study the kernelization complexity of structural parameterizations of...
research
∙
04/27/2020
An FPT-algorithm for recognizing k-apices of minor-closed graph classes
Let G be a graph class. We say that a graph G is a k-apex of G if G cont...
research
∙
04/23/2020
Coloring Problems on Bipartite Graphs of Small Diameter
We investigate a number of coloring problems restricted to bipartite gra...
research
∙
04/17/2020
Hitting forbidden induced subgraphs on bounded treewidth graphs
For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, fo...
research
∙
02/14/2020
On the complexity of finding large odd induced subgraphs and odd colorings
We study the complexity of the problems of finding, given a graph G, a l...
research
∙
09/30/2019
A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps
In the Directed Disjoint Paths problem, we are given a digraph D and a s...
research
∙
07/09/2019
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
For a fixed connected graph H, the {H}-M-DELETION problem asks, given a ...
research
∙
05/08/2019
Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
A matching cut is a partition of the vertex set of a graph into two sets...
research
∙
05/17/2018
Dual parameterization of Weighted Coloring
Given a graph G, a proper k-coloring of G is a partition c = (S_i)_i∈ [1...
research
∙
05/02/2018
Maximum cuts in edge-colored graphs
The input of the Maximum Colored Cut problem consists of a graph G=(V,E)...
research
∙
04/11/2018
Weighted proper orientations of trees and graphs of bounded treewidth
Given a simple graph G, a weight function w:E(G)→N∖{0}, and an orientati...
research
∙
10/17/2017