research
∙
07/26/2023
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
Recently, Hegerfeld and Kratsch [ESA 2023] obtained the first tight algo...
share
research
∙
07/10/2023
Tight Algorithmic Applications of Clique-Width Generalizations
In this work, we study two natural generalizations of clique-width intro...
research
∙
07/05/2023
Approximate Turing kernelization and lower bounds for domination problems
An α-approximate polynomial Turing kernelization is a polynomial-time al...
research
∙
02/27/2023
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
We study connectivity problems from a fine-grained parameterized perspec...
research
∙
02/07/2023
Tight algorithms for connectivity problems parameterized by clique-width
The complexity of problems involving global constraints is usually much ...
research
∙
12/23/2022
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
In this work we start the investigation of tight complexity bounds for c...
research
∙
09/28/2022
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width
Many computational problems admit fast algorithms on special inputs, how...
research
∙
07/15/2022
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
We study the parameterized problem of satisfying “almost all” constraint...
research
∙
02/14/2022
On Triangle Counting Parameterized by Twin-Width
In this report we present an algorithm solving Triangle Counting in time...
research
∙
11/05/2021
Directed flow-augmentation
We show a flow-augmentation algorithm in directed graphs: There exists a...
research
∙
07/13/2021
Towards exact structural thresholds for parameterized complexity
Parameterized complexity seeks to use input structure to obtain faster a...
research
∙
07/17/2020
Solving hard cut problems via flow-augmentation
We present a new technique for designing FPT algorithms for graph cut pr...
research
∙
04/27/2020
Approximate Turing Kernelization for Problems Parameterized by Treewidth
We extend the notion of lossy kernelization, introduced by Lokshtanov et...
research
∙
03/05/2020
Optimal Discretization is Fixed-parameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
research
∙
01/15/2020
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space
A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivi...
research
∙
01/14/2020
Efficient parameterized algorithms for computing all-pairs shortest paths
Computing all-pairs shortest paths is a fundamental and much-studied pro...
research
∙
06/26/2019
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
The area of parameterized approximation seeks to combine approximation a...
research
∙
05/09/2019
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
The Vertex Cover problem plays an essential role in the study of polynom...
research
∙
04/25/2019
On adaptive algorithms for maximum matching
In the fundamental Maximum Matching problem the task is to find a maximu...
research
∙
01/11/2019
On Kernelization for Edge Dominating Set under Structural Parameters
In the NP-hard Edge Dominating Set problem (EDS) we are given a graph G=...
research
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
05/12/2018
Bipartite Graphs of Small Readability
We study a parameter of bipartite graphs called readability, introduced ...
research
∙
04/26/2018
Efficient and adaptive parameterized algorithms on modular decompositions
We study the influence of a graph parameter called modular-width on the ...
research
∙
02/20/2018
The parameterized complexity of finding a 2-sphere in a simplicial complex
We consider the problem of finding a subcomplex K' of a simplicial compl...
research
∙
11/13/2017
Smaller parameters for vertex cover kernelization
We revisit the topic of polynomial kernels for Vertex Cover relative to ...
research
∙
03/25/2014