58 citations · 151 across the 35 of their papers we have counts for
7 papers · 1 filter
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…
Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra
Victor Lagerkvist, Magnus Wahlström
A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity par…
Structural Parameterizations of the Mixed Chinese Postman Problem
Gregory Gutin, Mark Jones, Magnus Wahlstrom
In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph ( may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each ed…
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
Gregory Gutin, Stefan Kratsch, Magnus Wahlström
The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by…
Hierarchies of Inefficient Kernelizability
Danny Hermelin, Stefan Kratsch, Karolina Sołtys +2
The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasona…
Parameterized Two-Player Nash Equilibrium
Danny Hermelin, Chien-Chung Huang, Stefan Kratsch +1
We study the computation of Nash equilibria in a two-player normal form game from the perspective of parameterized complexity. Recent results proved hardness for a number of varian…