58 citations · 239 across the 47 of their papers we have counts for
64 papers
Structural Parameterizations for Eternal Vertex Cover
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani +1
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph . To begin with, the defender places guards on vertices of . The attacker, on the…
On the Parameterized Complexity of Min-Sum-Radii
Pankaj Kumar, Haiko Müller, Sebastian Ordyniak +1
In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these…
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…
Optimal FPT-Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-appro…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki +1
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the pre…