Iterative compression とは

コンピュータサイエンスでは、反復圧縮は、各ステップの問題に1つの要素(グラフの頂点など)が追加される固定パラメータの扱いやすいアルゴリズムの設計のためのアルゴリズムテクニックであり、問​​題の以前の問題この追加は、ステップの後の問題に対する小さな解決策を見つけるのに役立ちます。
このテクニックは、Reed、Smith、Vettaによって、n個の頂点、m個のエッジ、および奇数サイクルトラバーサル番号kを持つグラフに対して、奇数サイクルトランスバーサルの問題が時間O(3k kmn)で解けることを示すために考案されました。奇数サイクルトランスバーサルは、各奇数サイクルから少なくとも1つの頂点を含むグラフの頂点の最小セットを見つける問題である。そのパラメータ化された複雑さは長年の未解決の問題でした。この技法は、後で固定パラメータの可読性の結果を示すのに非常に有用であることが判明した。これは、現在、パラメータ化されたアルゴリズムの分野における基本的技術の1つと考えられている。
反復圧縮は、奇数サイクルトランスバーサル(下を参照)およびエッジ二部化、フィードバック頂点セット、クラスタ頂点削除および有向フィードバック頂点セットなどの多くの問題でうまく使用されています。また、独立したセットの正確な指数関数時間アルゴリズムにも有効に使用されています。