Stefan Kratsch | DeepAI

AI Chat

Featured Co-authors

Daniël Paulusma
59 publications
Marcin Pilipczuk
51 publications
Dániel Marx
44 publications
Tomáš Masařík
39 publications
Matthew Alastair Johnson
35 publications
Shaohua Li
30 publications
Eun Jung Kim
29 publications
Manuel Sorge
28 publications
Martin Milanič
27 publications
Andreas Wiese
23 publications
Fabrizio Grandoni
22 publications

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

0 Narek Bojikian, et al. ∙

∙ 07/10/2023

Tight Algorithmic Applications of Clique-Width Generalizations

In this work, we study two natural generalizations of clique-width intro...

0 Vera Chekan, et al. ∙

∙ 07/05/2023

Approximate Turing kernelization and lower bounds for domination problems

An α-approximate polynomial Turing kernelization is a polynomial-time al...

0 Stefan Kratsch, et al. ∙

∙ 02/27/2023

Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth

We study connectivity problems from a fine-grained parameterized perspec...

0 Falko Hegerfeld, et al. ∙

∙ 02/07/2023

Tight algorithms for connectivity problems parameterized by clique-width

The complexity of problems involving global constraints is usually much ...

0 Falko Hegerfeld, et al. ∙

∙ 12/23/2022

Tight Bounds for Connectivity Problems Parameterized by Cutwidth

In this work we start the investigation of tight complexity bounds for c...

0 Narek Bojikian, et al. ∙

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

0 Stefan Kratsch, et al. ∙

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

0 Eun Jung Kim, et al. ∙

∙ 02/14/2022

On Triangle Counting Parameterized by Twin-Width

In this report we present an algorithm solving Triangle Counting in time...

0 Stefan Kratsch, et al. ∙

∙ 11/05/2021

Directed flow-augmentation

We show a flow-augmentation algorithm in directed graphs: There exists a...

0 Eun Jung Kim, et al. ∙

∙ 07/13/2021

Towards exact structural thresholds for parameterized complexity

Parameterized complexity seeks to use input structure to obtain faster a...

0 Falko Hegerfeld, et al. ∙

∙ 07/17/2020

Solving hard cut problems via flow-augmentation

We present a new technique for designing FPT algorithms for graph cut pr...

0 Eun Jung Kim, et al. ∙

∙ 04/27/2020

Approximate Turing Kernelization for Problems Parameterized by Treewidth

We extend the notion of lossy kernelization, introduced by Lokshtanov et...

0 Eva-Maria C. Hols, et al. ∙

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

0 Stefan Kratsch, et al. ∙

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

0 Falko Hegerfeld, et al. ∙

∙ 01/14/2020

Efficient parameterized algorithms for computing all-pairs shortest paths

Computing all-pairs shortest paths is a fundamental and much-studied pro...

0 Stefan Kratsch, et al. ∙

∙ 06/26/2019

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

The area of parameterized approximation seeks to combine approximation a...

0 Fabrizio Grandoni, et al. ∙

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

0 Eva-Maria C. Hols, et al. ∙

∙ 04/25/2019

On adaptive algorithms for maximum matching

In the fundamental Maximum Matching problem the task is to find a maximu...

0 Falko Hegerfeld, et al. ∙

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

0 Eva-Maria C. Hols, et al. ∙

∙ 10/16/2018

Multi-budgeted directed cuts

We study multi-budgeted variants of the classic minimum cut problem and ...

0 Stefan Kratsch, et al. ∙

∙ 05/12/2018

Bipartite Graphs of Small Readability

We study a parameter of bipartite graphs called readability, introduced ...

0 Rayan Chikhi, et al. ∙

∙ 04/26/2018

Efficient and adaptive parameterized algorithms on modular decompositions

We study the influence of a graph parameter called modular-width on the ...

0 Stefan Kratsch, et al. ∙

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

0 Benjamin Burton, et al. ∙

∙ 11/13/2017

Smaller parameters for vertex cover kernelization

We revisit the topic of polynomial kernels for Vertex Cover relative to ...

0 Eva-Maria C. Hols, et al. ∙

∙ 03/25/2014

Finding Shortest Paths between Graph Colourings

The k-colouring reconfiguration problem asks whether, for a given graph ...

0 Matthew Alastair Johnson, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world