activity
20092026
most citedCross-Composition: A New Technique for Kernelization Lower Bounds

114 citations · 306 across the 50 of their papers we have counts for

collaborators
Showing 2021Show all

2 papers · 1 filter

cs.DS2021

Flow-augmentation I: Directed graphs

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph , two vertices , and an…

cs.CC2021

Towards exact structural thresholds for parameterized complexity

Falko Hegerfeld, Stefan Kratsch

Parameterized complexity seeks to use input structure to obtain faster algorithms for NP-hard problems. This has been most successful for graphs of low treewidth: Many problems adm…