research
∙
08/30/2023
Data reduction for directed feedback vertex set on graphs without long induced cycles
We study reduction rules for Directed Feedback Vertex Set (DFVS) on inst...
share
research
∙
04/27/2023
On Solution Discovery via Reconfiguration
The dynamics of real-world applications and systems require efficient me...
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
∙
02/07/2023
First-Order Model Checking on Structurally Sparse Graph Classes
A class of graphs is structurally nowhere dense if it can be constructed...
research
∙
01/31/2023
Flipper games for monadically stable graph classes
A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...
research
∙
09/15/2022
Decomposition horizons: from graph sparsity to model-theoretic dividing lines
Let 𝒞 be a hereditary class of graphs. Assume that for every p there is ...
research
∙
08/30/2022
On the first-order transduction quasiorder of hereditary classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
research
∙
07/06/2022
Distributed domination on sparse graph classes
We show that the dominating set problem admits a constant factor approxi...
research
∙
06/29/2022
Combinatorial and Algorithmic Aspects of Monadic Stability
Nowhere dense classes of graphs are classes of sparse graphs with rich s...
research
∙
06/28/2022
Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
An indiscernible sequence (a̅_i)_1≤ i≤ n in a structure is an ordered se...
research
∙
05/02/2022
Token sliding on graphs of girth five
In the Token Sliding problem we are given a graph G and two independent ...
research
∙
04/22/2022
A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems
A graph vertex-subset problem defines which subsets of the vertices of a...
research
∙
03/31/2022
Transducing paths in graph classes with unbounded shrubdepth
Transductions are a general formalism for expressing transformations of ...
research
∙
11/29/2021
Local planar domination revisited
We show how to compute a 20-approximation of a minimum dominating set in...
research
∙
11/05/2021
Algorithms and data structures for first-order logic with connectivity under vertex failures
We introduce a new data structure for answering connectivity queries in ...
research
∙
07/13/2021
First-Order Logic with Connectivity Operators
First-order logic (FO) can express many algorithmic problems on graphs, ...
research
∙
05/08/2021
On set systems definable in sparse graph classes, discrepancy, and quantifier elimination
We study the (hereditary) discrepancy of definable set systems, which is...
research
∙
02/13/2021
Twin-width and permutations
Inspired by a width invariant defined on permutations by Guillemot and M...
research
∙
02/09/2021
Recursive Backdoors for SAT
A strong backdoor in a formula ϕ of propositional logic to a tractable c...
research
∙
12/04/2020
Constant round distributed domination on graph classes with bounded expansion
We show that the dominating set problem admits a constant factor approxi...
research
∙
10/06/2020
Towards an arboretum of monadically stable classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
research
∙
07/15/2020
Rankwidth meets stability
We study two notions of being well-structured for classes of graphs that...
research
∙
07/05/2020
Elimination distance to bounded degree on planar graphs
We study the graph parameter elimination distance to bounded degree, whi...
research
∙
03/26/2020
Regular partitions of gentle graphs
Szemeredi's Regularity Lemma is a very useful tool of extremal combinato...
research
∙
11/15/2019
Linear rankwidth meets stability
Classes with bounded rankwidth are MSO-transductions of trees and classe...
research
∙
10/01/2019
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of an optimization problem Q the input is a...
research
∙
09/15/2019
Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
The notion of nowhere dense graph classes was introduced by Nešetřil and...
research
∙
09/04/2019
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Classes with bounded rankwidth are MSO-transductions of trees and classe...
research
∙
03/01/2019
Parameterized Distributed Complexity Theory: A logical approach
Parameterized complexity theory offers a framework for a refined analysi...
research
∙
12/18/2018
Model-Checking on Ordered Structures
We study the model-checking problem for first- and monadic second-order ...
research
∙
11/16/2018
Progressive Algorithms for Domination and Independence
We consider a generic algorithmic paradigm that we call progressive expl...
research
∙
10/04/2018
First-order interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
research
∙
09/15/2018
Kernelization and approximation of distance-r independent sets on nowhere dense graphs
For a positive integer r, a distance-r independent set in an undirected ...
research
∙
07/10/2018
Polynomial bounds for centered colorings on proper minor-closed graph classes
For p∈N, a coloring λ of the vertices of a graph G is p-centered if for ...
research
∙
06/07/2018
Greedy domination on biclique-free graphs
The greedy algorithm for approximating dominating sets is a simple metho...
research
∙
05/09/2018
Parameterized circuit complexity of model checking first-order logic on sparse structures
We prove that for every class C of graphs with effectively bounded expan...
research
∙
02/27/2018