Kleinberg と Tardos による Algorithm Design ブックの演習問題を解いていたときに、エッジがグラフの MST に決して属さないという保証を見つけるという (私にとっては) それほど簡単ではない問題に出くわしました。質問は次のようになります。
各エッジ e にコスト c_e を持つグラフ G = (V, E) が与えられます。エラー パラメーター epsilon と k (両方とも > 0) が与えられた場合、次のプロパティ (*) が特定のエッジ e' = (u, v) に対して多項式時間で保持されるかどうかを確認したいと考えています。
(*) 各エッジのコストが最大でイプシロン (増加または減少) だけ変更され、e' 以外の k 個のエッジのコストが任意の異なる値にさらに変更されたとしても、エッジ e' は依然としてG のどの MST にも属していません。
MST の切断特性は知っていますが、それをこの問題に適用する方法がわかりません。事前にあなたのアイデアをありがとう！
j_random_hacker のコメントのおかげで、最終的に答えに達しました。
答えは、基本的に MST のサイクル プロパティを使用します。エッジが G のサイクルで最も高価なエッジである場合、G のどの MST にも属することはできません。
k 個のエッジのコストを任意の値に変更するための規定は、e' 自体を除いてすべてエッジ素である少なくとも k+1 サイクルで e' が最も高価なエッジであることを示さなければならないことを意味します。このように、k エッジの任意の変更によって e' が k サイクルで最も高価でなくても、最後のサイクルでは依然として最も高価になります。
グラフ G、エッジ e'、およびパラメーター k とイプシロン (両方 > 0) が与えられた場合:
e' よりも高価な G 内のすべてのエッジを一時的に削除します (これにより、見つけたサイクルで e' が最も高価になることが保証されます)。
ここで、e' の一方の端をソース (s) に、もう一方の端をシンク (t) に設定します。すべてのエッジの容量を 1 に設定します。フローの積分性により、すべての容量が整数であるため、積分フローが得られます。
少なくとも k+1 の値の流れが得られるかどうかを確認します。はいの場合、フロー分解は、フローの値と同じ数の s から t へのエッジ分離パスを提供します。これらすべてのパスに e' を追加してサイクルに変換します。このようにして、e' が最も高価なエッジであり、e' を除いてすべてエッジ分離である k+1 (またはそれ以上) のサイクルが得られます。これで、プロパティ (*) が e' に当てはまると安全に言えます。
整数の場合、イプシロンを処理する方法があります。ステップ 1 で、cost(e) + 2*epsilon よりも高価なすべてのエッジを削除します。