Search code examples
graph-theoryconnectivitymax-flow

edge-connectivity with constraints on number of vertices and removed edges

I need to find a subset G' of a graph G that can be disconnected from G by removing some edges. I have some constraints on number of vertices and edges

  1. Number of removed edges should be less than e
  2. Number of vertices in G' should be greater than v

I believe this problem should be a version of minimum-cut max-flow and/or edge-connectivity in graph theory. I wonder if there are already some studies (exact or heuristic alg) investigating this problem?

Any help or suggestions would be really appreciated.

Solution

  • A version of this problem has been studied in the literature as "vertex separator" and "edge separator" problems. There is still room for improvement. The followings are some useful links:

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

    I hope this helps.