On the complexity of the embedding problem for hypercube related graphs

www.sciencedirect.com

説　明　が　ウ　ン　チ　ー　コ　ン　グ

writerやめろ

概要

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

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

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

X3C

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

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

帰着

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

まず、カバーすべき集合をとしたとき、集合を考える。また、とする。

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

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

であることと同値。

としては上図のように構成する。上図のノード数はみやすさのため少なくなっているが、は実はになっており、たとえばはになっている。ポイントはノード数がたかだかの多項式のサイズなので、X3Cのインスタンスが与えられると多項式時間で構築できることである。

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

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

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

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

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

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

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