3 papers
cs.DS2026
Tight bounds for clique-packing parameterized by clique-width
Narek Bojikian, Stefan Kratsch
In the -Clique Packing problem, given a graph and an integer , we need to decide whether contains a set of pairwise vertex-disjoint cliques of size each. This…
cs.DS2026
Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
Benjamin Bergougnoux, Vera Chekan, Stefan Kratsch
In this work we contribute to the study of the fine-grained complexity of problems parameterized by multi-clique-width, which was initiated by Fürer [ITCS 2017] and pursued furthe…
cs.DS2025
Boundaried Kernelization via Representative Sets
Leonid Antipov, Stefan Kratsch
A kernelization is an efficient algorithm that given an instance of a parameterized problem returns an equivalent instance of size bounded by some function of the input parameter v…