Are there any known results on the complexity of finding a separator (of any size) satisfying a given property?

I know that a clique separator is easy (polynomial time) to find and also know that many papers consider the problem of finding small separators or separators that leave connected components of size at most a fraction of the size of the original graph. But what if one need a separator with other properties, say, a cubic, bipartite or 2-connected separator? It's also easy to create properties which are NP-hard to decide, hence it would be interesting to distinguish between the P and NPC cases.

Edit: Someone (which is not a user of this website) just told me that the problem is polynomial if the property is "has a universal vertex" and NP-complete if the property is "induces an independent set" or "induces a complete bipartite graph".

  • 6
    $\begingroup$ You should convince them to become a user of the site :) $\endgroup$ Commented Mar 7, 2012 at 22:23
  • 4
    $\begingroup$ Some senior people is resistant to new things ;) $\endgroup$ Commented Mar 7, 2012 at 22:49

2 Answers 2


Our paper:


shows that many of these problems are fixed-parameter tractable, i.e., we can decide in time f(k)*O(n+m) if an s-t separator of size k exists. This is true for example for the problem of finding a connected s-t separator, or a separator that is an independent set, or a separator that induces a bipartite graph. A forthcoming paper addresses the problem of finding a 2-connected s-t separator.


It is also hard to determine whether a graph has a cut that induces a disconnected graph, or a graph with exactly k components for all k>=2. On the other hand, connected cut is easy (that is k=1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.