Kernelization And Color Coding Techniques In Parameterized Algorithm

Kernelization and color coding are important techniques to design parameterized algorithms.Kernelization has been widely applied to the researches of the Cover,Packing and Cut problems.On the other hand, color coding has been applied to solve the Path,Packing,Matching and Graph Motif problems.Therefore,the study on kernelization and color coding is of guiding significance to solve the related problems.In this paper,we firstly studied the kemelization algorithms of P2-Packing problem.The current best result is the algorithm proposed by J.Wang etc.and got a kernel of size 7k using crown decomposition and local simplification.On this basis,we proposed two local optimization rules through further study on the structures of the P2-Packing problem.A kemelization algorithm denoted as P2PK with running time O(k³(n+m)) is also proposed.The analysis shows that the P₂-Packing problem has a kernel of size at most 6k.Based on the kernelization algorithm,we proposed a parameterized algorithm with running time O^*(2.371^3k),which improves the current best result.Moreover,we studied the scheme construction algorithms for color coloring.The current best result is the PH algorithm proposed by J.Chen etc.with running time O^*(6.1^k).The PH algorithm has the constraints that n is much larger than k and that k is a small parameter.On the other hand, the PBCC algorithm proposed by J.Wang etc.is only applied to the situations of n≤2k.On this basis,we proposed a hybrid architecture based color coding algorithm denoted as HABCC,which extended the applicability of color coding.We also analyzed the algorithm complexity and proved that the size upper bound of coloring scheme generated by the HABCC algorithm is 2k·[logk]^k-1·n.Compared with the PH algorithm, the HABCC algorithm constructs a coloring scheme of smaller size and is more practical.