The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree

Authors:

• Edyta Barbara Szymańska

Abstract

In this paper we prove that the problem of deciding whether a given k-uniform hypergraph H, with minimum (k−1)-wise vertex degree at least c|V(H)|, contains a matching missing exactly r vertices, that is, a set of disjoint edges of size (|V(H)|−r)/k, is NP-complete for c<[Formula presented], while for c>[Formula presented] and r>0 we provide a polynomial time algorithm for the corresponding search problem. For the perfect case, r=0, we show that the problem is NP-complete for c<[Formula presented] and give a polynomial time algorithm for c>[Formula presented] leaving a hardness gap in ([Formula presented],[Formula presented]). Our reduction carries over to the more general case when, for 1≤l≤k−1, the minimum l-wise codegree of a k-uniform hypergraph is considered. In particular, for k=3,l=1 and r=1 we deduce that the problem of deciding the existence of a perfect matching in a given k-uniform hypergraph H, with minimum degree at least c|V(H)|, is NP-complete for c<[Formula presented], complementing a fact proved recently in Han et al. (2009) [8] that the problem is trivial for c>[Formula presented]. In addition, we use our reduction to show that a problem of deciding the existence of a perfect packing of the cycle C₄⁽³⁾ into a 3-uniform hypergraph H with minimum 2-wise vertex degree at least c|V(H)| is NP-complete only for c<[Formula presented], which combined with a result from Kühn and Osthus (2006) [16] is, again, asymptotically tight.