Article ID Journal Published Year Pages File Type
4653834 European Journal of Combinatorics 2013 15 Pages PDF
Abstract
In addition, we use our reduction to show that a problem of deciding the existence of a perfect packing of the cycle C4(3) into a 3-uniform hypergraph H with minimum 2-wise vertex degree at least c|V(H)| is NP-complete only for c<14, which combined with a result from Kühn and Osthus (2006) [16] is, again, asymptotically tight.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
Authors
,