読者です 読者をやめる 読者になる 読者になる

P=NPだと夢がある。

kousuke.hatenablog.com
頂点に関してk-2tは極大グラフが1つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。

あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。
これは一緒に補グラフの最大独立問題をやってるに等しい。

少なくとも、NP完全問題が難しいのは、頂点に関するものと辺に関するものを両方一緒にやるからというのが現在の認識。
全部辺の問題に還元しながらやっていくのがたぶんよい。


追記
下記の資料をみていて、葉最大全域木でなんかインスピレーション湧いた。

www.slideshare.net

補グラフの辺は \frac{v(v-1)}{2} - mなんで、これを0に近づけていくと良いし、葉最大で葉を指定するのは難しいけど、次数使って辺をうまく重みづけできそうだし、その最小全域木に沿って処理できれば、Dinkelbach algorithmで結構高速にできそう。