Karolina Drabik

dblp:378/4961 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2026
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Artificial intelligence and machine learning · 1 · 1 first-author · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 33% Graph algorithms and graph theory · 33% Mathematical optimization · 17%

Topics — the 6 heaviest of 6, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Graph algorithms and graph theory › graph theory › graph parameters › graph width parameters
clique-width
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026
Mathematical optimization › combinatorial optimization
diverse solutions
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026
Graph algorithms and graph theory › graph theory › graph parameters
graph width parameters
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026
Logic in computer science
monadic second-order logic
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026
Computational complexity
parameterized complexity
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026
Computational complexity › parameterized complexity
structural parameters
1.012026
Finding Diverse Solutions Parameterized by Cliquewidth · AAAI 2026

Methods — techniques the papers use, named apart from their topics

dynamic programming · 1.0FPT algorithm · 1.0
YearPublicationVenuePosition
2026 Finding Diverse Solutions Parameterized by Cliquewidth
abstract
Finding a few solutions for a given problem that are diverse, as opposed to finding a single best solution to solve the problem, has recently become a notable topic in theoretical computer science. Recently, Baste, Fellows, Jaffke, Masařík, Oliveira, Philip, and Rosamond showed that under a standard structural parameterization by treewidth, one can find a set of diverse solutions for many problems with only a very small additional cost [Artificial Intelligence 2022]. In this paper, we investigate a much stronger graph parameter, the cliquewidth, which can additionally describe some dense graph classes. Broadly speaking, it describes graphs that can be recursively constructed by a few operations defined on graphs whose vertices are divided into a bounded number of groups, while each such group behaves uniformly with respect to any operation. We show that for any vertex problem, if we are given a dynamic program solving that problem on cliquewidth decomposition, we can modify it to produce a few solutions that are as diverse as possible with as little overhead as in the above-mentioned treewidth paper. As a consequence, we prove that a diverse version of any MSO1 expressible problem can be solved in linear FPT time parameterized by the cliquewidth, the number of sought solutions, and the number of quantifiers in the formula, which was a natural missing piece in the complexity landscape of structural graph parameters and logic for the diverse problems. We prove our results, allowing for a more general natural collection of diversity functions compared to only two mostly studied diversity functions previously. That might be of independent interest as a larger pool of different diversity functions can highlight various aspects of different solutions to a problem.
Karolina Drabik, Tomás Masarík
AAAI1