research
∙
09/20/2023
Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes
The celebrated notion of important separators bounds the number of small...
share
research
∙
09/03/2023
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Upward planarity testing and Rectilinear planarity testing are central p...
research
∙
06/29/2023
5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size
The notion of ℋ-treewidth, where ℋ is a hereditary graph class, was rece...
research
∙
07/01/2022
Search-Space Reduction via Essential Vertices
We investigate preprocessing for vertex-subset problems on graphs. While...
research
∙
06/20/2022
Finding k-Secluded Trees Faster
We revisit the k-Secluded Tree problem. Given a vertex-weighted undirect...
research
∙
06/09/2022
Kernelization for Feedback Vertex Set via Elimination Distance to a Forest
We study efficient preprocessing for the undirected Feedback Vertex Set ...
research
∙
02/04/2022
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
In the F-minor-free deletion problem we want to find a minimum vertex se...
research
∙
10/05/2021
Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size
In the ℱ-Minor-Free Deletion problem one is given an undirected graph G,...
research
∙
07/06/2021
On the Hardness of Compressing Weights
We investigate computational problems involving large weights through th...
research
∙
06/22/2021
Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
The goal of this paper is to open up a new research direction aimed at u...
research
∙
06/08/2021
FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
For a hereditary graph class ℋ, the ℋ-elimination distance of a graph G ...
research
∙
03/17/2021
Vertex Deletion Parameterized by Elimination Distance and Even Less
We study the parameterized complexity of various classic vertex deletion...
research
∙
09/17/2020
Sparsification Lower Bounds for List H-Coloring
We investigate the List H-Coloring problem, the generalization of graph ...
research
∙
09/17/2020
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
We introduce and study two natural generalizations of the Connected Vert...
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/19/2020
Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
We consider the Π-free Deletion problem parameterized by the size of a v...
research
∙
02/09/2020
Optimal polynomial-time compression for Boolean Max CSP
In the Boolean maximum constraint satisfaction problem - Max CSP(Γ) - on...
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
∙
06/13/2019
A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
For a fixed finite family of graphs F, the F-Minor-Free Deletion problem...
research
∙
02/05/2019
Hamiltonicity below Dirac's condition
Dirac's theorem (1952) is a classical result of graph theory, stating th...
research
∙
10/02/2018
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
We show that Odd Cycle Transversal and Vertex Multiway Cut admit determi...
research
∙
09/17/2018
Best-case and Worst-case Sparsifiability of Boolean CSPs
We continue the investigation of polynomial-time sparsification for NP-c...
research
∙
06/27/2018
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
Many combinatorial problems can be solved in time O^*(c^tw) on graphs of...
research
∙
06/27/2018
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Computing the smallest number q such that the vertices of a given graph ...
research
∙
04/24/2018
Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
We investigate polynomial-time preprocessing for the problem of hitting ...
research
∙
02/06/2018
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
The theory of kernelization can be used to rigorously analyze data reduc...
research
∙
07/06/2017