58 citations · 327 across the 60 of their papers we have counts for
71 papers
Biplanar graphs with independence number two are 9-colorable
Stefan Szeider
A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bou…
Enumerating Two-Orbit Graphs
David Seka, Stefan Szeider
We present an approach to enumerate graphs whose automorphism group has exactly two orbits. Our method exploits the observation that we can enumerate all graphs whose automorphism…
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…
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…
Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
Leroy Chew, Alexis de Colnet, Friedrich Slivovsky +1
Parity reasoning is challenging for Conflict-Driven Clause Learning (CDCL) SAT solvers. This has been observed even for simple formulas encoding two contradictory parity constraint…