Loading article…
コンピュータサイエンスにおいて、反復圧縮とは、固定パラメータの扱いやすいアルゴリズムを設計するためのアルゴリズム的手法であり、各ステップで問題に1つの要素（グラフの頂点など）が追加され、追加前の問題の小さな解が、ステップ後の問題の小さな解を見つけるのに役立てられる。
この手法は、n個の頂点、m個のエッジ、奇数サイクルの横断数kを持つグラフに対して、奇数サイクル横断問題がO (3 k kmn )の時間で解けることを示すために、リード、スミス、ベッタ [ 1 ] によって考案されました。奇数サイクル横断とは、すべての奇数サイクルから少なくとも 1 つの頂点を含むグラフの最小の頂点集合を見つける問題であり、そのパラメータ化された複雑さは長年の未解決問題でした。[ 2 ] [ 3 ]この手法は後に、固定パラメータの扱いやすさの結果 を示すのに非常に役立つことが証明されました。現在では、パラメータ化アルゴリズムの分野における基本的な手法の 1 つと考えられています。
反復圧縮は、例えば奇数サイクル横断（下記参照） 、エッジ二部分割、フィードバック頂点集合、クラスタ頂点削除など、多くの問題で成功裏に使用されてきました。 [ 4 ]また、独立集合の正確な指数時間アルゴリズム にも成功裏に使用されています。[ 5 ]
反復圧縮は、例えば、入力がグラフG = ( V , E )と自然数kであるパラメータ化されたグラフ問題に適用され、問題はサイズ≤ kの解 (頂点の集合) の存在をテストすることです。問題が次の特性を持つと仮定します。
これらの前提条件が満たされる場合、誘導部分グラフに頂点を1つずつ追加し、誘導部分グラフの解を求めることで問題を解決できます。手順は以下のとおりです。
このアルゴリズムは、圧縮サブルーチンを線形回数呼び出します。したがって、圧縮バリアントが固定パラメータ扱いやすい時間、つまり定数cに対してf ( k ) · n cで解ける場合、問題全体を解く反復圧縮手順はf ( k ) · n c +1時間で実行されます。同じ手法は、部分グラフ（誘導部分グラフではなく）で閉じられるグラフ特性のエッジセットを見つける場合や、グラフ理論以外の特性を見つける場合にも適用できます。パラメータkの値が不明な場合は、同じ反復圧縮アルゴリズムに基づいて各ステップを実行する指数探索または逐次探索の外側レベルを使用して、最適なkを選択することで見つけることができます。
グラフの奇数サイクル横断とは、グラフを二部グラフにするために削除できる頂点の集合のことです。Reed らは、元の論文で、グラフが最大kサイズの奇数サイクル横断を持つかどうかをO (3 k kmn )の時間で判定する反復圧縮アルゴリズムを示しました。その後、Lokshstanov、Saurabh、Sikdar らは、反復圧縮を用いたより単純なアルゴリズムを示しました。[ 6 ]サイズk + 1の削除セットYをサイズkの削除セットXに 圧縮するために、彼らのアルゴリズムは、Yの3 k +1分割すべてを 3 つのサブセットにテストします。新しい削除セットに属するYのサブセットと、 Xを削除した後に残る二部グラフの両側に属するYの 2 つのサブセットです。これらの 3 つのセットが選択されると、最大フロー最小カットアルゴリズムを適用することで、削除セットXの残りの頂点(存在する場合) を見つけることができます。
頂点被覆問題も、反復圧縮を適用できる例の一つです。頂点被覆問題では、グラフG = ( V , E )と自然数kを入力として受け取り、アルゴリズムは、すべての辺がX内の頂点に接続するようなk個の頂点の集合Xが存在するかどうかを判定する必要があります。この問題の圧縮版では、入力はグラフのすべての辺に接続するk + 1個の頂点の集合Yであり、アルゴリズムは、同じ性質を持つサイズkの集合Xが存在する場合、それを見つける必要があります。これを行う 1 つの方法は、 Yのどの部分集合を被覆から削除してグラフに再導入するかという2 k + 1通りの選択肢すべてをテストすることです。このような選択は、削除された 2 つの頂点が隣接していない場合にのみ有効であり、このような選択ごとに、サブルーチンは、この削除によって被覆されなくなる辺に接続するY の外側のすべての頂点を被覆に含める必要があります 。このサブルーチンを反復圧縮アルゴリズムで使用すると、頂点被覆のための単純なO (2 k n 2 )アルゴリズムが得られます。