最小最大匹配的紧密近似比及整数规划相关研究

### 最小最大匹配的紧密近似比及整数规划相关研究 #### 无权重最小最大匹配（Unweighted MMM） 从一个带有顶点权重函数 \(w\) 的图 \(G'_{\varPhi}\) 以及任意精度参数 \(\rho > 0\) 出发，我们要构建一个无权重图 \(G^{\rho}_{\varPhi}=(V^{\rho}, E^{\rho})\)，这个图的规模与 \(|\varPhi|\) 和 \(\frac{1}{\rho}\) 成多项式关系。 - **顶点集 \(V^{\rho}\) 的构建**：设 \(n = |V (G'_{\varPhi})| \cdot \frac{1}{\rho}\)，对于 \(G'_{\varPhi}\) 中的每个顶点 \(v\)，设置 \(n_v = \lceil n \cdot w(v) \rceil\)。新的顶点集由原顶点的多个副本组成，对于每个顶点 \(v\)，添加 \(4 \cdot n_v\) 个副本，即 \(V^{\rho} = \{ \langle v, i \rangle | v \in V (G'_{\varPhi}), i \in \{1, \ldots, 4 \cdot n_v\} \}\)。 - **边集 \(E^{\rho}\) 的构建**：边连接 \(G'_{\varPhi}\) 中相连顶点的副本对，即 \(E^{\rho} = \{ \{ \langle v_1, i_1 \rangle, \langle v_2, i_2 \rangle \} | \{v_1, v_2\} \in E(G_{\varPhi}), i_1 \in [4 \cdot n_{v_1}], i_2 \in [4 \cdot n_{v_2}] \}\)。 这种构建方式有相关性质：任何 \(G'_{\varPhi}\) 中的顶点覆盖 \(C\) 能产生一个乘积顶点覆盖 \(C^{\rho} = \bigcup_{v \in C} \{v\} \times [4 \cdot n_v]\)，且满足 \(| w(C) - \frac{|C^{\rho}|}{|V (G^{\rho}_{\varPhi})|} | < \rho\)（精度要求），并且 \(G^{\rho}_{\varPhi}\) 中的每个最小顶点覆盖都是乘积顶点覆盖。 接下来证明两个引理，以见证我们的归约的完备性和可靠性。 - **引理 7（可靠性）**：如果 \(\varPhi\) 是一个否实例，对于 \(G^{\rho}_{\varPhi}\) 中的每个最大匹配 \(M\)，有 \(2 \cdot |M| > |V (G^{\rho}_{\varPhi})| (1 - 2\gamma - \rho)\)。 - **证明过程**：取任意最大匹配 \(M\)，由它匹配的 \(2 \cdot |M|\) 个顶点构成一个顶点覆盖 \(C\)。通过移除 \(C\) 中不需要的顶点得到一个最小顶点覆盖 \(C^-\)，它是一个乘积顶点覆盖，这意味着存在 \(G'_{\varPhi}\) 中的顶点覆盖 \(C_w\)，其权重 \(w(C_w) < \frac{|C^-|}{V (G^{\rho}_{\varPhi})} + \rho \leq \frac{|C|}{V (G^{\rho}_{\varPhi})} + \rho\)。另一方面，根据引理 2 有 \(w(C_w) > 1 - 2\gamma\)。 - **引理 8（完备性）**：如果 \(\varPhi\) 是一个是实例，在 \(G^{\rho}_{\varPhi}\) 中存在一个最大匹配 \(M\)，使得 \(2 \cdot |M| < |V (G^{\rho}_{\varPhi})| (\frac{1}{2} + 2\epsilon + \rho)\)。 - **证明过程**：取引理 5 中构建的关于 \((G'_{\varPhi}, w_{min})\) 的分数匹配 \(F\)。当 \(F^0\) 以权重 \(F^0(u, v)\) 匹配顶点 \(u = (x, S_1)\) 和 \(v = (x, S_2)\) 时，我们使用平行边匹配 \(4 \cdot n \cdot \lceil F^0(u, v) \rceil\) 个 \(u\) 和 \(v\) 的副本。对于属于 \(G'_{\varPhi}\) 顶点覆盖且 \(0 < |S| < \frac{|R|}{2}\) 的顶点 \(u = (x, S) \notin I_S\)，它被 \(F^0\) 匹配到 \((x, S')\)，在 \(G^{\rho}_{\varPhi}\) 中留下 \(4 (\lceil w(x, S) \rceil - \lceil w(x, S') \rceil)\) 个未匹配的顶点，这个数能被 4 整除，从而可以根据 \(F^1\) 匹配二分 Kneser 图中所有顶点的副本。最后，\((x, \varnothing)\) 顶点的未匹配副本数能被 2 整除，我们可以复制 \(F^2\) 来匹配这些顶点的剩余副本。由于我们匹配了 \(G^{\rho}_{\varPhi}\) 顶点覆盖中的每个节点，所以这个匹配是最大的，其基数是顶点覆盖基数的一半，即 \(|M| = \frac{1}{2} (V (G^{\rho}_{\varPhi}) - |I_S|^{\rho}) < \frac{1}{2}V (G^{\rho}_{\varPhi}) (1 - (\frac{1}{2} - 2\epsilon - \rho))\)。