Gを、サイクルを含む重み付けされていない有向グラフとします。Gのすべての頂点とGのエッジのサブセットで構成され、G'を非巡回にするのに十分小さい、すべての非巡回グラフG'を検出/作成するアルゴリズムを探しています。
より形式的：目的のアルゴリズムはGを消費し、非巡回グラフSのセットを作成します。ここで、Sの各グラフG'は次の特性を満たします。
- G'にはGのすべての頂点が含まれます。
- G'は、G'が非巡回であるように、Gのエッジのサブセットを含みます。
- G'のエッジの数が最大になります。つまり、プロパティ1と2を満たすG''は存在しないため、G''にはG'よりも多くのエッジが含まれ、G''は非循環です。
背景：元のグラフGは、要素間のペアワイズ順序をモデル化しています。グラフのサイクルが原因で、これをすべての要素の順序として利用することはできません。したがって、最大非巡回グラフG'は、ペアごとの順序関係を可能な限り尊重しようとして、この順序の可能な限り最良の近似をモデル化する必要があります。
素朴なアプローチでは、エッジの可能なすべての組み合わせを削除し、削除するたびに非周期性をチェックすることができます。この場合、時間と空間の複雑さが悪いことを意味するバリエーションの強く分岐したツリーがあります。
注：問題はスパニングツリーに関連している可能性があり、G'グラフを一種の有向スパニングツリーとして定義できます。ただし、私のシナリオでは、G'のエッジのペアが同じ開始頂点または同じ終了頂点を持つ可能性があることに注意してください。これは、文献で使用されている有向スパニングツリーのいくつかの定義と矛盾します。
編集：スパニングツリーに関連する直感的な説明、背景情報、メモを追加しました。