Improved Parameterized Set Splitting Problem: A Probabilistic Approach

J. Chen, S. Lu. Improved Parameterized Set Splitting Problem: A Probabilistic Approach. Algorithmica. 2009; 54 (4):472-489.

n this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O *(2 k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O *(2.65 k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O *(4 k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable.s

Publication Year: 
2009
Faculty Author: 
Publication Credits: 
J. Chen, S. Lu
^