グリッドグラフの描画とか、horizontalとverticalしか使っちゃだめ系描画など、一般に「自由度が相対的に制限される」ようなセッティングにおける可能性判定の証明に使える気がする。 証明のテクは、「必ずこの配置しかありえない」ような配置を組み合わせ、…

arxiv.org ウ ン チ ー コ ン グ ！ グリッドに描画できるグラフのクラスをいろいろ考えて、PolynomialなものとNP-Completeなものに分けた。一般の描画はNP-Complete(そもそも木が無理なので) 次数がの要素のみからなるグラフを-Graphとよぶことにする。たと…

タイトル練り直せ www.sciencedirect.com Theorem 最大次数が4の木をグリッドに埋め込めるかはNP-Complete 証明 not-all-equal 3satに帰着する。これは、3CNF式が与えられたときに、各clauseに少なくともひとつfalseになるリテラルが含まれるように充足可能…