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
∙
08/11/2023
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
We study the parameterized complexity of two classic problems on directe...
research
∙
07/13/2023
Planar Disjoint Paths, Treewidth, and Kernels
In the Planar Disjoint Paths problem, one is given an undirected planar ...
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
∙
05/05/2023
Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
In Chordal/Interval Vertex Deletion we ask how many vertices one needs t...
research
∙
01/15/2023
Long Directed Detours: Reduction to 2-Disjoint Paths
We study an "above guarantee" version of the Longest Path problem in dir...
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
∙
03/17/2021
Vertex Deletion Parameterized by Elimination Distance and Even Less
We study the parameterized complexity of various classic vertex deletion...
research
∙
11/16/2020
To Close Is Easier Than To Open: Dual Parameterization To k-Median
The k-Median problem is one of the well-known optimization problems that...
research
∙
02/09/2020
Optimal polynomial-time compression for Boolean Max CSP
In the Boolean maximum constraint satisfaction problem - Max CSP(Γ) - on...
research
∙
07/15/2019
Inapproximability within W[1]: the case of Steiner Orientation
In the k-Steiner Orientation problem we are given a mixed graph, that is...
research
∙
09/16/2018
Constant factor FPT approximation for capacitated k-median
Capacitated k-median is one of the few outstanding optimization problems...
research
∙
07/27/2018
Connected Components at Scale via Local Contractions
As a fundamental tool in hierarchical graph clustering, computing connec...
research
∙
04/07/2018
Random Order Contention Resolution Schemes
Contention resolution schemes have proven to be an incredibly powerful c...
research
∙
04/06/2018
Subquadratic Approximation Scheme for Partition
The subject of this paper is the time complexity of approximating Knapsa...
research
∙
04/04/2018
Losing Treewidth by Separating Subsets
We study the problem of deleting the smallest set S of vertices (resp.ed...
research
∙
07/06/2017