Projects per year
Abstract
Given two k-graphs H and F, a perfect F-packing in H is a collection of vertex-disjoint copies of F in H which together cover all the vertices in H. In the case when F is a single edge, a perfect F-packing is simply a perfect matching. For a given fixed F, it is often the case that the decision problem whether an n-vertex k-graph H contains a perfect F-packing is NP-complete. Indeed, if k≥3, the corresponding problem for perfect matchings is NP-complete [17,7] whilst if k=2 the problem is NP-complete 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 F-packings 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 k-graph 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 F-packing; (iii) We also prove a similar result for perfect K-packings in k-graphs where K is a k-partite k-graph. 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 NP-complete.
Original language | English |
---|---|
Pages (from-to) | 72-104 |
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