114 citations · 306 across the 50 of their papers we have counts for
4 papers · 1 filter
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Falko Hegerfeld +1
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van G…
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width
Stefan Kratsch, Florian Nelles
Many computational problems admit fast algorithms on special inputs, however, the required properties might be quite restrictive. E.g., many graph problems can be solved much faste…
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula over a fixed, finite Boolean constraint language , with or without weights. Mo…
On Triangle Counting Parameterized by Twin-Width
Stefan Kratsch, Florian Nelles, Alexandre Simon
In this report we present an algorithm solving Triangle Counting in time , where n and m, respectively, denote the number of vertices and edges of a graph G and d denote…