距離限定部分グラフ探索問題に対する近似アルゴリズム

摘要

グラフG=（V，E）中の頂点集合S{is contained in}Vを考える．S中の任意の頂点u，vの組に対して，G中での視とvの間の距離が高々dである場合にSはd-クリークであると言う．また，Sにより誘導されるGの部分グラフの直径が高々dの場合には，Sはd-クラブであると言う．与えられたn頂点グラフに対して，MAX d-CLIQUE問題（またはMAX d-CLUB問題）の目的は，G中の最大d-クリーク（または最大d-クラブ）を発見することである．任意のε＞0に対して，MAX 1-CLIQUEとM_(AX) 1-CLUBは，P=NPでない限り多項式時間でn~(1-ε)-近似できない．なぜならば，これらの問題はM_(AX) C_(LIQUE)と同じ問題であり，MAX CLIQUEがP=NPでない限り多項式時間でn~(1-ε)-近似できないからである（［5］，［10］）．さらに，任意の固定されたd≥2と任意のε＞0に対して，MAX d-CLUBはP＝NP，でない限りn~(1/2-ε)-近似できないことも知られている［2］．MAX d-CLUBの近似上界に関しては，任意の偶数d≥2に対する多項式時間0（n~(1/2)）-近似アルゴリズムが著者らのグループにより提案されている［2］．しかしながら，奇数d≥3に対しては，このアルゴリズムの近似率はO（n~(2/3)）に悪化するため，近似下界Ω（n~(1/2-ε）との乖離が依然として残っている［2］．本稿ではまず，MAX d-CLUBの近似上界の改善を行う．すなわち，任意の奇数d≥3に対して多項式時間O（n~(1/2)）-近似アルゴリズムを提案する．そして同様のアイデアを用いて，任意のd≥2に対してMAX d-CLIQUEも多項式時間でO（n~(1/2)）-近似できることを示す．それとともにP＝NPでない限り，任意のε＞0に対して，MAX d-CLIQUEもn~(1/2-ε)-近似できないことについて述べる．