58 citations · 239 across the 47 of their papers we have counts for
7 papers · 1 filter
Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable.…
Exact Algorithms for Clustered Planarity with Linear Saturators
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta +3
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an -vertex planar graph whose vertices are partitioned into independent sets (called clus…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis
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…
From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Eduard Eiben, Robert Ganian, Iyad Kanj +2
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular…
Solving Quantified Boolean Formulas with Few Existential Variables
Leif Eriksson, Victor Lagerkvist, George Osipov +3
The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. Many problems of central interest in AI are…
A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Mueller, Sebastian Ordyniak +2
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that lin…