近似(3)

引き続きVazirani本４章。
Multiway cutとMinimum k-cutの近似アルゴリズムについて。
Multiway cutはk個のterminal集合が与えられたときに、
あるcutを取り除くと、各terminalが別々の連結成分に属するような、
最小重みのcutを求める問題。k>=3でNP困難である。(k=2はminimum s-t cutなので多項式)
k-cutは、取り除くとk個以上の連結成分ができるような最小重みのcutを求める問題。
kを固定すると多項式、入力の一部にするとNP困難である。
両者とも2-2/k近似をこの章では示していて、前者はmaxflow、
後者はGomory-Hu Treeを用いている。

まだ簡単なので、電車の中でさらさら読んでいけるけど、
だんだん難しくなってきてるね。