私は次の問題で立ち往生しています。加重有向グラフGが与えられた場合、Gのすべての負の（単純な）サイクルを含むGの最小部分グラフを作成したいと思います。
Bellman-Fordを使用して負のサイクルを見つける方法を知っています。また、有向グラフの単純なサイクルの数が指数関数的であることを知っています。
この問題に取り組むための素朴な方法の1つは、すべての単純なサイクルを単純に繰り返し、負のサイクルを選択することですが、多項式時間アルゴリズムがあるのではないかと感じています。私がグーグルを通して見つけたほとんどの記事は、（すべてではなく）負のサイクルを見つけることについてでした。
多項式時間の解法に向けたヒント、または多項式時間で解けないことを証明するためのヒントを提供する可能性のあるスタックオーバーフローに関する専門家をここで見つけたいと思っています。
よろしくお願いします！
乾杯、ロバート
同様の問題に興味がある、または立ち往生している人のために：それはNP完全です。cstheoryのスレッドを教えてくれたwichに感謝します。
NP完全である理由を確認するには、まず、問題が次のように記述される可能性があることに注意してください。N個の頂点とG上のエッジEを持つ重み付き有向グラフGが与えられた場合、Eが（単純な）負のサイクルにあるかどうかを調べます。含まれている場合、EはサブグラフHに含まれている必要があります。含まれていない場合、EはHに含まれていてはなりません。
ここで、エッジEを重みwのE =（u、v）とします。W + w <0となるような総重みWのvからuへのパスがあるかどうかを知りたいです。これを多項式時間で行うことができれば、多項式時間でハミルトン閉路問題を解くこともできます。
エッジEにN-1.00001の重みを割り当てます。グラフ内の他のすべてのエッジに-1の重みを割り当てます。ここで、Eが存在するグラフの唯一の負のサイクルは、すべての頂点を含むサイクル（そのサイクルの重みは-0.00001）であり、したがってハミルトン閉路です。
一緒に考えてくれてありがとう！