Complexity of finding a graph separator with a given property
Our paper:

http://arxiv.org/abs/1110.4765

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.