P=NPだと夢がある。
kousuke.hatenablog.com
頂点に関しては極大グラフが１つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。
あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。
これは一緒に補グラフの最大独立問題をやってるに等しい。
少なくとも、NP完全問題が難しいのは、頂点に関するものと辺に関するものを両方一緒にやるからというのが現在の認識。
全部辺の問題に還元しながらやっていくのがたぶんよい。
追記
下記の資料をみていて、葉最大全域木でなんかインスピレーション湧いた。
補グラフの辺はなんで、これを0に近づけていくと良いし、葉最大で葉を指定するのは難しいけど、次数使って辺をうまく重みづけできそうだし、その最小全域木に沿って処理できれば、Dinkelbach algorithmで結構高速にできそう。
追記2
最大クリーク問題である条件下で、多項式時間で計算量一気に短縮できる処理があって、それを常に続けられると多項式時間になるのになぁとおもっている。
