問題: Q-正則無向グラフが与えられた場合、エッジ削除によって N-正則無向サブグラフを識別するアルゴリズムを探しています。N < Q (明らかに) であり、N-regular サブグラフの空間をサンプリングする必要があるため、アルゴリズムにある程度のランダム性を実装できることが重要です。
私が試したこと: これまでのところ、私の最善の方法は、ハミルトニアン サイクルを見つけて、サイクルの他のすべてのエッジを削除することでした。これは (Q-1)-regular サブグラフを適切に作成し、原則として、必要な程度の規則性に達するまで繰り返すことができます。または、ハミルトン サイクルのないグラフをうっかり作成してしまいます。ただし、このアプローチは遅く (これが私の主な問題です)、それ以外の場合は完全に不必要なハミルトン サイクルの制限に依存していることに少し問題があります。
私の質問: 誰でもハミルトン サイクル アプローチの代替案を提案できますか、それとも問題が本質的に困難であり、ハミルトン サイクル検出よりも高速な解決策はありそうもないことを教えてもらえますか? ここでいくつかのグラフ理論の概念をいじっていることはわかっていますが、それをより正式に組み立てる専門知識がないことを残念に思います。
お時間をいただきありがとうございます:)
編集: 元のネットワークの頂点の数 (= L) が偶数であることを忘れていました。L と Q の両方が奇数の場合は不可能であり、Q の制限をできるだけ少なくしたいため、通常のグラフを確実に作成できるようにするためにこの制限を設けました。2 つ目は、すべての頂点を保持したいということです (したがって、エッジの削除についてのみ言及しました)。