1 Search Results for "Gan, Luyining"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.64

The Decision Problem for Perfect Matchings in Dense Hypergraphs

Authors: Luyining Gan and Jie Han

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

Given 1 ≤ 𝓁 < k and δ ≥ 0, let PM(k,𝓁,δ) be the decision problem for the existence of perfect matchings in n-vertex k-uniform hypergraphs with minimum 𝓁-degree at least δ binom(n-𝓁,k-𝓁). For k ≥ 3, the decision problem in general k-uniform hypergraphs, equivalently PM(k,𝓁,0), is one of Karp’s 21 NP-complete problems. Moreover, for k ≥ 3, a reduction of Szymańska showed that PM(k, 𝓁, δ) is NP-complete for δ < 1-(1-1/k)^{k-𝓁}. A breakthrough by Keevash, Knox and Mycroft [STOC '13] resolved this problem for 𝓁 = k-1 by showing that PM(k, k-1, δ) is in P for δ > 1/k. Based on their result for 𝓁 = k-1, Keevash, Knox and Mycroft conjectured that PM(k, 𝓁, δ) is in P for every δ > 1-(1-1/k)^{k-𝓁}. In this paper it is shown that this decision problem for perfect matchings can be reduced to the study of the minimum 𝓁-degree condition forcing the existence of fractional perfect matchings. That is, we hopefully solve the "computational complexity" aspect of the problem by reducing it to a well-known extremal problem in hypergraph theory. In particular, together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for 𝓁 ≥ 0.4k.

Cite as

Luyining Gan and Jie Han. The Decision Problem for Perfect Matchings in Dense Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.ICALP.2022.64,
  author =	{Gan, Luyining and Han, Jie},
  title =	{{The Decision Problem for Perfect Matchings in Dense Hypergraphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.64},
  URN =		{urn:nbn:de:0030-drops-164057},
  doi =		{10.4230/LIPIcs.ICALP.2022.64},
  annote =	{Keywords: Computational Complexity, Perfect Matching, Hypergraph}
}

Refine by Author
1 Gan, Luyining
1 Han, Jie

Refine by Classification
1 Theory of computation → Complexity classes

Refine by Keyword
1 Computational Complexity
1 Hypergraph
1 Perfect Matching

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Gan, Luyining"

The Decision Problem for Perfect Matchings in Dense Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message