对顶点数和删除的边数有限制的边连通性

Question

我需要找到图 G 的子集 G'，该子集可以通过删除一些边与 G 断开连接。我对顶点和边的数量有一些限制

1. 删除的边数应小于e
2. G'中的顶点数应大于v

我认为这个问题应该是图论中最小割最大流and/or边连通性的一个版本。我想知道是否已经有一些研究（精确或启发式算法）调查这个问题？

如有任何帮助或建议，我们将不胜感激。

Answer 1

这个问题的一个版本在文献中被研究为 "vertex separator" 和 "edge separator" 问题。仍有改进的余地。以下是一些有用的链接：

1. https://www.sciencedirect.com/science/article/pii/002001909290140Q
2. https://link.springer.com/article/10.1007/s10107-005-0574-7

希望对您有所帮助。