边缘连接性受顶点数和移除的边缘的限制

Question

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

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

我相信这个问题应该是图论中最小切割最大流量和/或边连接的一种形式。我想知道是否已经有一些研究（精确或启发式算法）来研究此问题？

任何帮助或建议都将不胜感激。

Answer 1

此问题的一个版本在文献中已被研究为“顶点分隔符”和“边缘分隔符”问题。仍有改进的空间。以下是一些有用的链接：

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

我希望这会有所帮助。