The complexity of perfect matchings and packings in dense hypergraphs

Autor(es)

Han, Jie ^[1] ; Treglown, Andrew ^[2]

Afiliação do(s) autor(es)

^[1] Univ Rhode Isl, Dept Math, Kingston, RI 02881 - USA

^[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 141, p. 72-104, MAR 2020.
• Citações Web of Science: 0

Resumo

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 <= l <= k-1 , we give a minimum l-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 l, 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. (C) 2019 The Authors. Published by Elsevier Inc. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado