Complexity of the H-factor problem.

Definitions and mathematical statement

Fix a nonempty finite simple graph $H$ with $h$ vertices and a real density parameter $0<c<1$. An $H$-factor of a finite simple graph $G$ is a family of pairwise vertex-disjoint subgraphs isomorphic to $H$ whose vertex sets cover $V(G)$. Copies need not be induced: additional edges among or between their vertices may be ignored. Necessarily $h$ divides $|V(G)|$.

Consider the decision problem whose input is an $n$-vertex graph $G$ promised to satisfy $\delta(G)\ge cn$, and whose output specifies whether an $H$-factor exists. The graph $H$ and constant $c$ are fixed, rather than part of the growing input. The inequality means $\delta(G)\ge\lceil cn\rceil$. Inputs violating divisibility can be rejected immediately.

The source’s complexity question asks for which choices of $H$ and $c$ this promised problem is NP-hard, and for which choices a polynomial-time decision algorithm exists. Hardness is under polynomial-time many-one reductions whose output graphs satisfy the degree promise; running-time exponents and constants in an algorithm may depend on the fixed parameters.

This is a parameter-dependent classification, rather than a universal assertion of hardness for all $H,c$. For example, a one-edge factor is the perfect-matching problem, and sufficiently strong density hypotheses can guarantee factors in other cases. Values $c\ge1$ would give an empty simple-graph promise. The unresolved target includes the precise transition between algorithmic and hard regimes, with equality at a critical density treated separately when necessary.

Short English statement

Classify, for each fixed graph H and density c, the computational difficulty of finding whether a dense graph has a perfect packing by copies of H.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3284 (OPG-46738), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Complexity of the H-factor problem.. Original problem and discussion. http://www.openproblemgarden.org/op/complexity_of_the_h_factor_problem.
• S3 J. Han and A. Treglown, The complexity of perfect matchings and packings in dense hypergraphs. https://arxiv.org/abs/1609.06147.