二部グラフを非循環にするアルゴリズムの設計に関して質問がありました。誰かがここで私を助けてくれることを願っています。問題文は次のとおりです。
無向二部グラフ G = (U,V,E) を考えます。ここで、U = {u_1, u_2, ...u_M} は M ノードのセットであり、V = {v_1, v_2, ..., v_N} はE は、U のノードを V のノードに接続するエッジのセットです。簡単にするために、グラフが接続されており、循環している、つまり循環があると仮定します。
目的は、次のようにサイクルを排除し、グラフをツリーまたはフォレストに縮小するアルゴリズムを設計することです。アルゴリズムはラウンドで進みます。ラウンドは、U 内の各ノード u_i、i = 1、2、...、M を選択し、それに接続されているエッジを削除することで記述されます。ノード u_i が孤立している (つまり、接続されているエッジがない) 場合は、それを無視して続行します。このようにして、各ラウンドで最大 M 個のエッジが削除されます。あるラウンドの終わりにグラフがツリーまたはフォレストに縮小すると、アルゴリズムは停止します。
ラウンド数が最小になるようにラウンドを設計するための多項式時間アルゴリズム（M、N）が可能かどうかを知りたい（グラフをツリー/フォレストに縮小するため）。