## 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_{4}^{(3)} 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.

- Record ID
- UAM1708574f17854d03a065f488e15d8c22
- Author
- Journal series
- European Journal of Combinatorics, ISSN 0195-6698
- Issue year
- 2013
- Vol
- 34
- Pages
- 632-646
- ASJC Classification
- DOI
- DOI:10.1016/j.ejc.2011.12.009 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 30
- Score source
- journalList
- Score
- Publication indicators
- = 6; : 2013 = 1.423; : 2013 (2 years) = 0.612 - 2013 (5 years) =0.732

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM1708574f17854d03a065f488e15d8c22/

- URN
`urn:amu-prod:UAM1708574f17854d03a065f488e15d8c22`

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.