# Complexity of finding a graph separator with a given property

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".

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