research
∙
09/14/2023
Dynamic programming on bipartite tree decompositions
We revisit a graph width parameter that we dub bipartite treewidth, alon...
share
research
∙
04/27/2023
Universal Obstructions of Graph Parameters
We introduce a graph-parametric framework for obtaining obstruction char...
research
∙
04/10/2023
Approximating branchwidth on parametric extensions of planarity
The branchwidth of a graph has been introduced by Roberson and Seymour a...
research
∙
02/14/2023
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Disjoint-paths logic, denoted 𝖥𝖮+𝖣𝖯, extends first-order logic (𝖥𝖮) with...
research
∙
12/19/2022
Excluding Single-Crossing Matching Minors in Bipartite Graphs
By a seminal result of Valiant, computing the permanent of (0,1)-matrice...
research
∙
11/03/2022
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (...
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
∙
07/20/2022
Contraction Bidimensionality of Geometric Intersection Graphs
Given a graph G, we define bcg(G) as the minimum k for which G can be co...
research
∙
07/14/2022
Kernelization for Graph Packing Problems via Rainbow Matching
We introduce a new kernelization tool, called rainbow matching technique...
research
∙
07/11/2022
Killing a Vortex
The Structural Theorem of the Graph Minors series of Robertson and Seymo...
research
∙
04/22/2022
The mixed search game against an agile and visible fugitive is monotone
We consider the mixed search game against an agile and visible fugitive....
research
∙
01/15/2022
On Strict Brambles
A strict bramble of a graph G is a collection of pairwise-intersecting c...
research
∙
12/14/2021
Edge-trewidth: Algorithmic and combinatorial properties
We introduce the graph theoretical parameter of edge treewidth. This par...
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
∙
06/07/2021
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
In general, a graph modification problem is defined by a graph modificat...
research
∙
05/03/2021
A Constant-factor Approximation for Weighted Bond Cover
The Weighted ℱ-Vertex Deletion for a class F of graphs asks, weighted gr...
research
∙
04/07/2021
Parameterized Complexity of Elimination Distance to First-Order Logic Properties
The elimination distance to some target graph property P is a general gr...
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/02/2021
Block Elimination Distance
We introduce the block elimination distance as a measure of how close a ...
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/26/2021
Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs
We introduce the rendezvous game with adversaries. In this game, two pla...
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
∙
09/08/2020
Edge Degeneracy: Algorithmic and Structural Results
We consider a cops and robber game where the cops are blocking edges 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/24/2020
A linear fixed parameter tractable algorithm for connected pathwidth
The graph parameter of pathwidth can be seen as a measure of the topolog...
research
∙
04/16/2020
Hcore-Init: Neural Network Initialization based on Graph Degeneracy
Neural networks are the pinnacle of Artificial Intelligence, as in recen...
research
∙
07/12/2019
Planar Disjoint Paths in Linear Time
The Disjoint Paths problem asks whether a fixed number of pairs of termi...
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
∙
07/05/2019
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
For a finite collection of graphs F, the F-TM-Deletion problem has as ...
research
∙
10/27/2018
Minimum Reload Cost Graph Factors
The concept of Reload cost in a graph refers to the cost that occurs whi...
research
∙
09/21/2018
Data-compression for Parametrized Counting Problems on Sparse graphs
We study the concept of compactor, which may be seen as a counting-analo...
research
∙
08/02/2018
Lean tree-cut decompositions: obstructions and algorithms
The notion of tree-cut width has been introduced by Wollan [The structur...
research
∙
05/11/2018
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
We consider the problems of deciding whether an input graph can be modif...
research
∙
04/29/2018
Partial complementation of graphs
A partial complement of the graph G is a graph obtained from G by comple...
research
∙
03/26/2018