graph-theory - n個の頂点を持つグラフの場合、k個の頂点に依存しないセットを見つけるための多項式時間アルゴリズムはありますか？

Question

n個の頂点を持つグラフの場合、k個の頂点に依存しないセットを見つけるにはどうすればよいですか？（実際には、n = 200、k = 10の妥当な時間で実行される限り、多項式時間アルゴリズムである必要はありません。）

Answer 1

kが固定されていない場合、これはNP困難な問題です。kが固定されている場合、それは自明な多項式です。また、他のオーバーフローサイトの1つで、純粋なアルゴリズムの質問をすることをお勧めします。

実用的なアルゴリズムについては、すでに何を試しましたか？欲張り検索のような単純なものでも、小さな問題サイズで機能する可能性があります。