Fixed Parameter Set Splitting, Linear Kernel and Improved Running Time

Abstract

We study the problem k-Set Splitting in fixed parameter complexity. We show that the problem can be solved in time O ∗ (2.6494 k), improving on the best currently known running time of O ∗ (8 k). This is done by showing that a non-trivial instance must have a small minimal Set Cover, and using this to reduce the problem to a series of small instances of Max Sat. We also give a linear kernel containing 2k elements and 2k sets. This is done by reducing the problem to a bipartite graph problem where we use crown decomposition to reduce the graph. We show that this result also gives a good kernel for Max Cut. 1