www.sciencedirect.com
概要
グラフ
がcubicalであるとは、あるhypercubeが存在して、そのsubgraphとなることをいう。が与えられたとき、がcubicalであるか判定するのはNP-Complete
hypercube
頂点番号が
から
からなり、頂点番号のbinary表現で1bitだけ異なる頂点間に辺が張られている。
証明
描画はNAE3SAT!!!で常勝！ｗと思っていたけど今回はEXACT COVERをしている。すげ絵
EXACT COVERインスタンスをcubical埋め込みオラクルによって解くことで示している。
Theorem 1
がcubicalであることと、がproper coloringを持つことは同値
連結な
-Graphの辺彩色がevenであるとは、どの色についても偶数回現れることをいう。の辺彩色がproperであるとは、の部分グラフである連結な-Graphが、サイクルである場合、そしてその場合に限りevenであることをいう。
構築
まず、いま考えているEXACT COVERの問題を整理する。
集合
の部分集合の族
を考え、の各要素を含むの要素はちょうど3個ある。いま、のdisjointな部分族で、をちょうどカバーするものがあるかどうか調べたい。
まず、の各要素について、hexagonを作る。hexagonの上の辺同士を長方形でつなぐ。こうすると、proper coloringをもつとき、上の辺はすべて同じ色になる。
次に各の要素について、それらに含まれる要素たちのhexagonの下3辺のうちどれか同士をladderで結ぶ。このとき、ladderの長さは、hexagonの上の長方形をたどって(上の1辺は通らない)、移動するときのコスト+2とする。これは一見複雑に見えるが、結んだ下の辺たちが同じ色になるように調整するためだけの理由。
あとは、これにproper coloringが存在するかを考えればいい。hexagonの上の辺のcolor (全部同じ)を0とすると、下3辺のうち、ちょうど1辺だけが0になりえる。0になった辺たちが、EXACT COVERに対応する。
逆にEXACT COVERが存在するときは、それに対応して割当を構築できる。
感想
これもかなり天才構築でびっくりする。研究は天才以外お断りパズル論文コンテストなのか
