Dealing with several parameterized problems by random methods

In this paper, we apply random methods to deal with several parameterized problems. For the Parameterized Weighted P 3 -Packing problem, by randomly partitioning the vertices in given graph, a tripartite graph can be obtained. We prove that the Parameterized Weighted P 3 -Packing problem can be solved in polynomial time on tripartite graphs. Based on the algorithm on tripartite graphs, a randomized parameterized algorithm of running time O ⁎ ( 32 k ) is given for the Parameterized Weighted P 3 -Packing problem. For the Parameterized Weighted Load Coloring problem, by randomly partitioning the vertices in given graph into two parts and studying the structure properties of the connected components in two parts, a randomized parameterized algorithm of running time O ⁎ ( 11. 32 k ) is presented. For the Parameterized Claw-free Edge Deletion problem on Diamond-free Graphs, by combining random with branching methods, a parameterized algorithm of running time O ⁎ ( 2. 42 k ) is given.

Authors

• Qilong Feng
• Neng Huang
• Xiong Jiang
• Jianxin Wang

Keywords

• Random methods
• Parameterized P 3 -Packing
• Parameterized Load Coloring
• Parameterized Claw-free Edge Deletion