Research On Parameterized Algorithms For Packing And Matching Problems

As a new method solving NP-hard problems, parameter computation method has attracted lots of attention, and has been used to solve hard problems in many fields. Packing and Matching problems form an important class of NP-hard problems, which have great applications in the fields of scheduling and code optimization. In particular, 3D-Matching problem is one of the six basic NP-complete problems. This dissertation is mainly focused on the Packing and Matching problems such as 3-Set Packing problem, Weighted 3-Set Packing problem, Weighted 3D-Matching problem, Weighted rD-Matching problem, Weighted r-Set Packing problem, Weighted P2-Packing problem, aiming at developing new algorithmic methods for Packing and Matching problems. The related research results are presented in the following.In this dissertation, we take 3-Set Packing problem as an example to study the relationship between problem solution and problem special instances. By further analyzing solution structure, the solving of 3-Set Packing problem is closely related to the solving of two special problem instances. By solving the two special instances,3-Set Packing problem can be solved deterministically in time O*(3.533k), improving the previous best result O*(4.613k).For Weighted 3-Set Packing problem, the relationship between problem instance and solution is studied, which results in the dividing of problem instance into two parts. Based on the structure analysis, a deterministic algorithm of time O*(10.6)3k is presented for Weighted 3-Set Packing problem. Moreover, by further analyzing the structure of the (k+1)-Packing, a deterministic parameterized algorithm of time O*(7.563k) can be obtained, improving the previous best result O*(12.83k).For Weighted 3D-Matching problem, a special property can be obtained: there exist two columns in k-matching such that at least 2k/3 elements of those two columns are contained in a (k+l)-matching. Based on the above property, a deterministic parameterized algorithm of time O*(4.823k) can be obtained for Weighted 3D-Matching problem, improving the previous best result 0*(5.473k).Dividing and sorting technique are used to design efficient algorithms for Weighted rD-Matching and Weighted r-Set Packing problems. For a given instance of Weighted rD-Matching problem (S, k), divide the elements in the first column. By enumerating the n possible dividings, there must exist a dividing such that k/2 elements of the first column of the maximum weighted k-Matching are divided into one part, and the other k/2 elements are divided into the other part. Then by dividing the other (r—1)k elements of the maximum weighted k-Matching efficiently, a deterministic algorithm of time O*f(4(r-1)k+o(k)) can be obtained, improving the previous best result O*(4rk+o(k)). The algorithm for weighted rD-Matching problem can be used to solve unweighted 3D-Matching problem to get a deterministic algorithm of time O*(16k+o(k)), improving the previous best result O*(21.26k), which is the current best result for unweighted 3D-Matching problem.For Weighted r-Set Packing problem, sort the r-sets in given instance by the element of minimum value in each r-set. Based on the property after sorting, there must exist a dividing for the maximum weighted k-Packing such that exact k/2 elements of the maximum weighted k-Packing are divided into one part. By dividing the remaining (2r—1)k/2 elements efficiently, a deterministic algorithm of time O*(2(2r-1)k+o(k)) can be obtained, improving the previous best result O*(22rk+o(k)). The algorithm for weighted r-Set Packing problem can be used to solve unweighted 3-Set Packing problem with running time O*(32k+O(k)), improving the previous best result O*(4.613k), which is the current best result for unweighted 3-Set Packing problem.For Weighted P2-Packing problem, in order to solve the Weighted P2-Packing problem more efficiently, the weighted version of vertex-disjoint S-path is studied. First, the properties of the weighted vertex-disjoint S-path in bipartite graph are presented. Based on the properties obtained, the weighted vertex-disjoint S-path in bipartite graph can be used to design efficient algorithm for the Weighted P2-Packing problem, which results in a deterministic algorithm of time O*(8k). The algorithm proposed for the Weighted P2-Packing problem can be used to solve the unweighted P2-Packing problem, which results in a deterministic algorithm of time O*(8k), improving the previous best result O*(14.67k). The alogirthm proposed in this dissertation for P2-Packing problem is the current best result.In conclusion, this dissertation focuses on the deterministic parameterized algorithms design for Packing and Matching problems. By further analyzing the structure of 3-Set Packing problem, Weighted 3-Set Packing problem, Weighted 3D-Matching problem, Weighted rD-Matching problem, Weighted r-Set Packing problem, Weighted P2-Packing problem, efficient deterministic parameterized algorithms are given. The research methods and results in this dissertation enrich the methods solving Packing and Matching problems, which have significant meaning in solving NP-hard problems.