algorithm - 通过边删除创建规则子图

Question

问题:给定一个 Q 正则无向图，我正在寻找一种算法来通过边删除来识别 N 正则无向子图。 N < Q(显然)，重要的是可以在算法中实现某种程度的随机性，因为我需要对 N 个正则子图的空间进行采样。

我尝试过的:到目前为止，我最好的方法是找到哈密顿环，并删除环上的所有其他边。这很好地创建了一个 (Q-1)-regular 子图并且原则上可以重复直到达到所需的规则程度，或者我无意中创建了一个没有哈密顿循环的图。然而，这种方法很慢(这是我的主要问题)，而且它依赖于哈密顿循环的其他完全不必要的限制，这有点问题。

我的问题:任何人都可以建议哈密顿循环方法的替代方法，或者只是告诉我这个问题本质上很难，而且不太可能有比哈密顿循环检测更快的解决方案？我意识到我在这里涉及一些图论概念，但恐怕我没有专业知识来更正式地构建它。

感谢您的宝贵时间:)

编辑:忘了说原来网络的顶点数(=L)是偶数。我做了这个限制以确保可以创建一个规则的图形，因为如果 L 和 Q 都是奇数，这是不可能的，我希望对 Q 的限制尽可能少。其次，我确实希望保留所有顶点(因此我只提到删除边)。

Answer 1

在this article ，作者提供了一种将特殊的 Q-regular 图转换为 Q-1 - regular 的方法，时间复杂度为 O(n^3) ，这意味着对于某些特殊情况，您的问题可以在 O(n^4) 中解决。您可能想看看这篇文章，看看它是否对您有帮助。