マルチターミナルカットの複雑さ

マルチターミナルカット問題では、エッジ重み付きグラフと、ターミナルと呼ばれる頂点の部分集合が与えられ、各ターミナルを他のすべてから分離する最小重みのエッジ集合を求められます。ターミナルの数kが2の場合、これは単に最小カット・最大フロー問題であり、多項式時間で解くことができます。k = 3の時、問題はNP困難であることが示されていますが、任意の固定kに対して平面グラフの場合は多項式時間で解けます。ただし、kが固定されていない場合、平面問題はNP困難になります。任意のグラフに対する簡単な近似アルゴリズムも説明されており、最適カット重みに対して{2 - 2 / k}の範囲に収束することが保証されています。