We study the complexity of bounded variants of graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-parite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of O(k/(ln k)) unless P = NP. This improves the previous factor of k/(2~(O(k/(ln k)~（1/2)) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of 54/53 - ε, 30/29 - ε and 23/22 -ε for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of k-Set-Packing and the problem of Maximum Independent-Set in (k + 1)-claw-free graphs.
展开▼
