Inapproximability of 6-Matching in k-Uniform Hypergraphs

摘要

In this paper we analyze the complexity of the maximum cardinality 6-matching problem in k-uniform hypergraphs. 6-matching is the following problem: for a given 6 ∈ N and a hypergraph H = (V, ε), |V| = n, a subset M (C) ε with maximum cardinality is sought so that no vertex is contained in more than 6 hyperedges of M. The b-matching problem is a prototype of packing integer programs with right-hand side b ≥ 1. It has been studied in combinatorics and optimization. Positive approximation results are known for b ≥ 1 and /c-uniform hypergraphs (Krysta 2005) and constant factor approximations for general hypergraphs for b = Ω(log n), (Srinivasan 1999, Srivastav, Stangier 1996, Raghavan, Thompson 1987), but the inapproximability of the problem has been studied only for b = 1 and k-uniform and k-partite hypergraphs (Hazan, Safra, Schwartz 2006). Thus the range from b ∈ [2, log n] is almost unexplored. In this paper we give the first inapproximability result for k-uniform hypergraphs: for every 2 ≤ b ≤ k/ log k there no polynomial-time approximation within any ratio smaller than Ω(k/(b log k)), unless P = NP. Our result generalizes the result of Hazan, Safra and Schwartz from b = 1 to any fixed 2 ≤ b ≤ k/log k and k-uniform hypergraphs. But the crucial point is that for the first time we can see how b influences the non-approximability. We consider this result as a necessary step in further understanding the non-approximability of general packing problems. It is notable that the proof of Hazan, Safra and Schwartz cannot be lifted to b ≥ 2. In fact, some new techniques and ingredients are required; the probabilistic proof of the existence of a hypergraph with "almost" disjoint b-matching where dependent events have to be decoupled (in contrast to Hazan et al.) and the generation of some sparse hypergraph.