<p>Our paper:</p>

<p><a href="http://arxiv.org/abs/1110.4765">http://arxiv.org/abs/1110.4765</a></p>

<p>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.</p>

CC BY-SA 3.0
2012-03-07T19:03:24.623Z
2012-03-07T19:03:24.623Z
Daniel Marx
<p>It is also hard to determine whether a graph has <a href="http://arxiv.org/pdf/1104.4779v2.pdf">a cut that induces a disconnected graph</a>, or a graph with <a href="http://rutcor.rutgers.edu/~mkaminski/preprints/Parameterizing%20cut%20sets%20in%20a%20graphs%20by%20the%20number%20of%20their%20components.pdf">exactly k components for all k>=2</a>. On the other hand, connected cut is easy (that is k=1). </p>

CC BY-SA 3.0
2012-03-08T07:41:51.173Z
2012-03-08T07:41:51.173Z
Marcin Kamiński
<p>Are there any known results on the complexity of finding a separator (of any size) satisfying a given property?</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-03-07T22:23:04.383Z
You should convince them to become a user of the site :)
Suresh Venkat
CC BY-SA 3.0
2012-03-07T22:49:46.363Z
Some senior people is resistant to new things ;)
Vinicius dos Santos
<ds.algorithms><graph-theory><graph-algorithms>
Complexity of finding a graph separator with a given property
Vinicius dos Santos
# Complexity of finding a graph separator with a given property

(Asked by: username_0 on 2012-03-07)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: You should convince them to become a user of the site :)  
> **username_0**: Some senior people is resistant to new things ;)  

---

## 2 answers

### Answer by username_2 on 2012-03-07. Score: 8 | Accepted answer

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.


---

### Answer by username_3 on 2012-03-08. Score: 7

It is also hard to determine whether a graph has [a cut that induces a disconnected graph](http://arxiv.org/pdf/1104.4779v2.pdf), or a graph with [exactly k components for all k>=2](http://rutcor.rutgers.edu/~mkaminski/preprints/Parameterizing%20cut%20sets%20in%20a%20graphs%20by%20the%20number%20of%20their%20components.pdf). On the other hand, connected cut is easy (that is k=1).


---

