概要

「木 $T$ と、正整数 $k$ が与えられたとき、 $T$ を $k$ 次元hypercubeに埋め込めるか」という判定問題はNP-Complete.

まあこれが成り立つので、 $T$ はより一般にグラフ $G$ に拡張できる。

証明がExact Cover by 3-sets (X3C)によるもので、これまたテクニカル

X3C

集合 $X$ の部分集合で、サイズ3のものをいくつか集めた集合 $C$ が与えられる(Cは集合の集合)。 $C$ の部分集合で、 $X$ のdisjointな分割になっているもの $C'$ が存在するか(このとき $C'$ は $X$ をカバーしている)

これはNP-Completeらしい。 $X$ の要素数が3の倍数でない場合は明らかに不可能なので3の倍数個としてよい。

帰着

X3Cインスタンスが与えられたときに、木 $T$ と $k$ をうまく構築して、「木が $k$ 次元hypercubeに埋め込める」ことと「X3Cインスタンスが解をもつ」ことを同値にしたい。

f:id:xuzijian629:20191225183835p:plain

まず、カバーすべき集合を $X$ としたとき、集合 $S = X \cup {z}$ を考える。また、 $k = |S|$ とする。

木 $T$ が $k$ 次元に埋め込めるかは、 $T$ のノードに、 $S$ の部分集合を割り当てたときに、

異なるノードについて異なる部分集合が割り当てられており
隣接するノードについて、部分集合のset differenceの大きさが1

であることと同値。

$T$ としては上図のように構成する。上図のノード数はみやすさのため少なくなっているが、 $X$ は実は $x_1, \ldots, x_{3q}$ になっており、たとえば $XX$ は $x_1x_1, \ldots, x_{3q}x_{3q}$ になっている。ポイントはノード数がたかだか $3q + 1 = |S|$ の多項式のサイズなので、X3Cのインスタンスが与えられると多項式時間で構築できることである。

図で $R$ の説明がものすごく雑だけど、 $R$ は $q$ 要素で、それぞれ $XXX$ 型の部分集合が割り当てられている。 $C_4$ ノードが $XXX\backslash C$ の型を持っているので、 $XXX$ 型は $C_4$ と $R$ に限られる。もし、 $T$ のノードに割り当てられる集合がすべて異なるなら、 $R \subset C$ が成り立つ。

$R$ と $C_8$ の辺のつなぎ方も重要で、とりあえず $R$ の $i$ 番目のノードに割り当てる部分集合を $x_{3i - 2}x_{3i-1}x_{3i}$ にしておく。これは本当はこうならないかも知れないけど、 $x_k$ のネーミングはあとで適当にある順列によって差し替えることができるので、気にしなくていい。

とりあえずこれで構築は完了

X3Cインスタンスに解がある場合

解 $C'$ は $q$ 要素からなるので、 $R$ と $C_8$ を結ぶ辺は、 $R$ の $j$ 番目の要素とつながっている $C_8$ の要素のラベルを、 $C'$ の $j$ 番目の集合にすればいい。このとき、明らかにノードのラベルは全ノードで異なっているので、 $T$ は $k$ -cubeに埋め込むことができる。

X3Cインスタンスに解がない場合

つまりどう選んでも、 $C'$ の各要素(集合)がdisjointにならない場合。 $R$ が要素数が $q'$ のtex: Cの役割を果たしているので、もし埋め込めるとしたら、そういう $C'$ が見つかって矛盾。