The Complexity of Perfect Packings in Dense Graphs

Autor(es)

Han, Jie ; Gopal, TV ; Jager, G ; Steila, S

• Tipo de documento: Artigo Científico
• Fonte: THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017); v. 10185, p. 15-pg., 2017-01-01.

Resumo

Let H be a graph of order h and let G be a graph of order n such that h vertical bar n. A perfect H-packing in G is a collection of vertex disjoint copies of H in G that covers all vertices of G. Hell and Kirk-patrick showed that the decision problem whether a graph G has a perfect H-packing is NP-complete if and only if H has a component which contains at least 3 vertices. We consider the decision problem of containment of a perfect H-packing in graphs G under the additional minimum degree condition. Our main result shows that given any gamma > 0 and any n-vertex graph G with minimum degree at least (1 - 1/chi(cr)(H) + gamma)n, the problem of determining whether G has a perfect H-packing can be solved in polynomial time, where chi(cr)(H) is the critical chromatic number of H. This answers a question of Yuster negatively. Moreover, a hardness result of Kuhn and Osthus shows that our main result is essentially best possible and closes a long-standing hardness gap for all complete multi-partite graphs H whose second smallest color class has size at least 2. (AU)

• 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
• 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: 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