Dimitrios M. Thilikos

research

∙ 09/14/2023

Dynamic programming on bipartite tree decompositions

We revisit a graph width parameter that we dub bipartite treewidth, alon...

0 Lars Jaffke, et al. ∙

research

∙ 04/27/2023

Universal Obstructions of Graph Parameters

We introduce a graph-parametric framework for obtaining obstruction char...

0 Christophe Paul, et al. ∙

research

∙ 04/10/2023

Approximating branchwidth on parametric extensions of planarity

The branchwidth of a graph has been introduced by Roberson and Seymour a...

0 Dimitrios M. Thilikos, et al. ∙

research

∙ 02/14/2023

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes

Disjoint-paths logic, denoted 𝖥𝖮+𝖣𝖯, extends first-order logic (𝖥𝖮) with...

0 Nicole Schirrmacher, et al. ∙

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...

0 Archontia C. Giannopoulou, et al. ∙

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 (...

0 Petr A. Golovach, et al. ∙

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...

0 Laure Morelle, et al. ∙

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...

0 Julien Baste, et al. ∙

research

∙ 07/14/2022

Kernelization for Graph Packing Problems via Rainbow Matching

We introduce a new kernelization tool, called rainbow matching technique...

0 Stéphane Bessy, et al. ∙

research

∙ 07/11/2022

Killing a Vortex

The Structural Theorem of the Graph Minors series of Robertson and Seymo...

0 Dimitrios M. Thilikos, et al. ∙

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....

0 Guillaume Mescoff, et al. ∙

research

∙ 01/15/2022

On Strict Brambles

A strict bramble of a graph G is a collection of pairwise-intersecting c...

0 Emmanouil Lardas, et al. ∙

research

∙ 12/14/2021

Edge-trewidth: Algorithmic and combinatorial properties

We introduce the graph theoretical parameter of edge treewidth. This par...

0 Loïc Magne, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Eun Jung Kim, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Julien Baste, et al. ∙

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...

0 Julien Baste, et al. ∙

research

∙ 03/02/2021

Block Elimination Distance

We introduce the block elimination distance as a measure of how close a ...

0 Öznur Yaşar Diner, et al. ∙

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...

0 Ignasi Sau, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/12/2021

A more accurate view of the Flat Wall Theorem

We introduce a supporting combinatorial framework for the Flat Wall Theo...

0 Ignasi Sau, et al. ∙

research

∙ 09/08/2020

Edge Degeneracy: Algorithmic and Structural Results

We consider a cops and robber game where the cops are blocking edges of ...

0 Stratis Limnios, et al. ∙

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...

0 Ignasi Sau, et al. ∙

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...

0 Mamadou Moustapha Kanté, et al. ∙

research

∙ 04/16/2020

Hcore-Init: Neural Network Initialization based on Graph Degeneracy

Neural networks are the pinnacle of Artificial Intelligence, as in recen...

14 Stratis Limnios, et al. ∙

research

∙ 07/12/2019

Planar Disjoint Paths in Linear Time

The Disjoint Paths problem asks whether a fixed number of pairs of termi...

0 Petr A. Golovach, et al. ∙

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 ...

0 Julien Baste, et al. ∙

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 ...

0 Petr A. Golovach, et al. ∙

research

∙ 10/27/2018

Minimum Reload Cost Graph Factors

The concept of Reload cost in a graph refers to the cost that occurs whi...

0 Julien Baste, et al. ∙

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...

0 Eun Jung Kim, et al. ∙

research

∙ 08/02/2018

Lean tree-cut decompositions: obstructions and algorithms

The notion of tree-cut width has been introduced by Wollan [The structur...

0 Archontia C. Giannopoulou, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 04/29/2018

Partial complementation of graphs

A partial complement of the graph G is a graph obtained from G by comple...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/26/2018

Clustering to Given Connectivities

We define a general variant of the graph clustering problem where the cr...

0 Petr A. Golovach, et al. ∙

Dimitrios M. Thilikos

Featured Co-authors