Projects per year
Abstract
Given two kgraphs H and F, a perfect Fpacking in H is a collection of vertexdisjoint copies of F in H which together cover all the vertices in H. In the case when F is a single edge, a perfect Fpacking is simply a perfect matching. For a given fixed F, it is often the case that the decision problem whether an nvertex kgraph H contains a perfect Fpacking is NPcomplete. Indeed, if k≥3, the corresponding problem for perfect matchings is NPcomplete [17,7] whilst if k=2 the problem is NPcomplete in the case when F has a component consisting of at least 3 vertices [14]. In this paper we give a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect Fpackings is polynomial time solvable. We then give three applications of this tool: (i) Given 1≤ℓ≤k−1, we give a minimum ℓdegree condition for which it is polynomial time solvable to determine whether a kgraph satisfying this condition has a perfect matching; (ii) Given any graph F we give a minimum degree condition for which it is polynomial time solvable to determine whether a graph satisfying this condition has a perfect Fpacking; (iii) We also prove a similar result for perfect Kpackings in kgraphs where K is a kpartite kgraph. For a range of values of ℓ,k (i) resolves a conjecture of Keevash, Knox and Mycroft [20]; (ii) answers a question of Yuster [47] in the negative; whilst (iii) generalises a result of Keevash, Knox and Mycroft [20]. In many cases our results are best possible in the sense that lowering the minimum degree condition means that the corresponding decision problem becomes NPcomplete.
Original language  English 

Pages (fromto)  72104 
Number of pages  33 
Journal  Journal of Combinatorial Theory. Series B 
Volume  141 
Early online date  19 Jul 2019 
DOIs  
Publication status  Published  Mar 2020 
Keywords
 perfect matching
 absorbing method
 complexity
Fingerprint
Dive into the research topics of 'The complexity of perfect matchings and packings in dense hypergraphs'. Together they form a unique fingerprint.Projects
 1 Finished

EPSRC Fellowship: Dr Andrew Treglown  Independence in groups, graphs and the integers
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils