9
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ You should convince them to become a user of the site :) $\endgroup$ – Suresh Venkat Mar 7 '12 at 22:23
  • 4
    $\begingroup$ Some senior people is resistant to new things ;) $\endgroup$ – Vinicius dos Santos Mar 7 '12 at 22:49
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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