An FPT algorithm with a running time of O(n4+2O(k)n2.5) is described for the SET SPLITTING problem, parameterized by the number k of sets to be split. It is also shown that there can be no FPT algorithm for this problem with a running time of the form 2o(k)nc unless the satisfiability of n-variable 3SAT instances can be decided in time 2o(n).

Additional Metadata
Citation
Dehne, F, Fellows, M.R. (Michael R.), & Rosamond, F.A. (Frances A.). (2003). An FPT algorithm for set splitting.