X3C-Y

X3C 问题

实例： 有限集合 $S$，$|S|=3q$，以及S的三元素子集的集合 $C$

询问： $C$ 中是否包含 $S$ 的严格覆盖。即是否存在子集 $C'\subseteq C$，使得 $S$ 中每个元素都恰好出现在$C'$的一个成员中。

X3C-Y 问题在 X3C 问题之上额外添加了一个约束条件：

令 $C = \{c_1,c_,...,c_n\}$，对任意 $i,j,i \neq j, |c_i \cap c_j|<=1$

注意由于是集合，因此三元素集合 C 中的任意两个元素的交集的最大大小为 2，不可能是 3（3 说明两个元素完全相等，这在集合中不可能存在）

NPC 证明

构造 X3C 实例 $S$，$C$，其中

$S=\{a_1,a_2,...,a_{3q}\}, |S| = 3q$

$C=\{c_1,c_2,...,c_k\}, |C|=k$

在此基础上构建 X3C-Y 实例 $T$，$D$。

新增 $6k$ 个元素, 分别编号为 $b_{1,1},b_{1,2},...,b_{1,6},...,b_{2,1},b_{2,6},...,b_{k,1},b_{k,6}$，则

$T = S \cup \{b_{1,1},b_{1,2},...,b_{1,6},...,b_{2,1},b_{2,6},...,b_{k,1},b_{k,6}\}$

对 D 的构建，将 C 中每一个元素，相应替换为 D 中的 五个元素，替换如下：

将 $c_i=\{a_{f(i)}, a_{g(i)}, a_{h(i)}\}$ 替换为

$d_{i,1} = \{a_{f(i)}, b_{i,1}, b_{i,4}\}$

$d_{i,2} = \{a_{g(i)}, b_{i,2}, b_{i,5}\}$

$d_{i,3} = \{a_{h(i)}, b_{i,3}, b_{i,6}\}$

$d_{i,4} = \{b_{i,1}, b_{i,2}, b_{i,3}\}$

$d_{i,5} = \{b_{i,4}, b_{i,5}, b_{i,6}\}$

显然，上述变换可以在多项式时间内完成

ps: 注意区分 $b$ 和 $d$，$b$ 是新增的布尔变量元素，$d$ 是新增的项元素， $b$ 每一个项新增 6 个， $d$ 每一个项变换出 5 个

(->) 若 X3C 中存在 $C'$ 是 $S$ 的严格覆盖，则 X3C-Y 实例中的严格覆盖 $D'$ 可以按照如下方式选择：

• $C'$ 中每一个 $c_i$ 元素对应选择 $D$ 集合中的三个元素 $d_{i,1},d_{i,2},d_{i,3}$ 。此时 $T$ 中来自原 $S$ 的所有元素均出现一次，且和 $c_i$ 对应的所有的 $b_{i,1}\sim b_{i,6}$ 均出现一次。

• 对于还未被选中的所有 $b$，也即对 $C-C'$ 中的每一个元素 $c_j$，选择 $D$ 集合的两个元素 $d_{j,4},d_{j,5}$。

上述两个步骤选择出的元素构成的子集 $D'$ 可以构成对 T 的严格覆盖。

(<-) 若 X3C-Y 中存在 $D'$ 是 T 的严格覆盖，对于同一个 j 对应的五个元素 $d_{j,1}\sim d_{j,5}$，可得要么同时选中 $d_{j,1}\sim d_{j,3}$，要么同时选中 $d_{j,4},d_{j,5}$ 两个。

此时令严格匹配 D' 中的每三个元素 $d_{j,1}\sim d_{j,3}$ 对应选择原 X3C 问题中的 $c_j$，可得该种方式构成的子集 $C'$，恰好为对 $S$ 的严格覆盖。

上述说明比较难以理解，下面通过一个简单的例子来说明对应过程：

例如，
X3C 实例项集合为 C = {c1-c5}，5个元素，那么相应构建的 X3C-Y 实例的项集合即为 D={d1(1-5),d2(1-5),...,d5(1-5)}，共 25 个元素

假如可以找到一个 X3C 的严格覆盖  C'={c1,c3,c5}，那么X3C-Y 的严格覆盖 D' 就是 {d1(1-3),d3(1-3),d5(1-3), d2(4-5),d4(4-5)}，反之同理。

ps2： issue#4 鉴于 X3C-Y 是 X3C 的子问题，是否有必要证明其必要性？ 及其讨论。

ps3： issue#9 X3C-Y 实例和 X3C 实例对应关系的讨论