56、均匀超图中几乎完美匹配的复杂性

均匀超图中几乎完美匹配的复杂性

1. 研究背景与动机

在超图理论中，寻找完美匹配和几乎完美匹配是重要的研究问题。近期的研究为这一领域带来了新的进展和启发。

一方面，对于特定类别的超图，有研究将其转化为局部搜索算法来寻找完美匹配。例如，K¨uhn 等人证明了在某些 3 - 均匀超图中，满足一定条件时存在完美 $C_4$ - 填充，尽管未提及具体算法，但证明有可能被算法化。Czygrinow 和 Nagle 以及 Pikhurko 研究了满足类似余度条件的 3 - 均匀超图的几乎完美 $K_4^{(3)}$ - 填充。

另一方面，Dirac 在 1952 年证明了对于图中哈密顿循环存在性这一原本 NP - 完全的问题，在图的最小度 $\delta(G) \geq |V(G)|/2$ 时变得简单。对于 $k$ - 均匀超图，图的最小度 $\delta(G)$ 可由最小（$l$ - wise）度 $\delta_l(H)$ 替代，其中 $1 \leq l \leq k - 1$，$\delta_l(H)$ 是使得 $H$ 中每个 $l$ 元顶点集至少包含在 $d$ 条边中的最大整数 $d$。R¨odl 等人给出了 $k$ - 均匀超图 $H$ 中存在完美匹配的充分条件，用 $\delta_{k - 1}(H)$ 表示。对于大的 $n$ 且 $n$ 能被 $k$ 整除，他们完全确定了 $t(k, n) := t(k, k - 1, n)$ 的值，该值接近 $n/2 - k$。

2. 问题定义

定义了一类决策问题 $APM_l(k, r, c)$，它是 $APM(k, r)$ 的受限版本。给定整数 $k \geq 3$，$0 < l <