7 papers
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…
Parameterized Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the Min--Lin problem: given a system of length- linear equations modulo , find of minimum cardinality such that is satisfiable…