<p>This is an edited version of a previous "answer" which incorrectly claimed a polynomial-time algorithm for the problem. What I write below is a connection to an existing problem which suggests that the problem is difficult.</p>

<p>Let $s,t$ be two nodes in $G$ and we want to check if they are $(a,b)$-connected. That is removing any $a$ nodes and any $b$ edges should not disconnect $s$ and $t$. Another way to look at it as follows: what is the minimum number of nodes that we need to remove to reduce the edge-connectivity between $s$ and $t$ to $b$? These type of problems have been studied under the name multi-route cuts and they are dual to multi-route flows. Various approximation results have been shown though many basic problems are not yet resolved. A result of interest is the following. Suppose each edge has a cost $c(e)$ and we wish to remove the minimum-cost set of edges to reduce the edge-connectivity between $s$ and $t$ to $b$; then this problem is NP-Hard when $b$ is part of the input. This result is in the paper by Barman and Chawla: <a href="http://arxiv.org/abs/0908.0350">http://arxiv.org/abs/0908.0350</a></p>

<p>Two papers that will appear in upcoming SODA 2012 are on multi-route cuts which have further results on the topic. The one by Chuzhoy etal has hardness results for some variants. </p>

CC BY-SA 3.0
2011-12-16T03:00:34.023Z
The Chuzhoy etal paper is now available on the ArXiv: http://arxiv.org/abs/1112.3611
Chandra Chekuri
CC BY-SA 3.0
2011-12-14T02:32:38.787Z
2011-12-15T03:57:59.877Z
2011-12-15T03:57:59.877Z
Chandra Chekuri
<p>Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the standard definition, is $(k-1,0)$-connected, according to the new definition. Is there a polynomial-time algorithm to decide if $G$ is $(a,b)$-connected? Here I consider that the input is $G$, $a$ and $b$.</p>

CC BY-SA 3.0
2011-12-13T17:23:32.117Z
Homework problem?
Chandra Chekuri
CC BY-SA 3.0
2011-12-13T17:57:32.553Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2011-12-13T17:58:20.650Z
ps: it would help if you provide some background and motivation for the question if you think the question is in cstheory's scope.
Kaveh
CC BY-SA 3.0
2011-12-13T18:30:17.140Z
I came to this question during a talk of Janez Zerovnik about connectivity of networks about 2/3 years. To be honest, I do not remember the details. Since then, I have asked about 4 researchers and nobody saw how to reduce it to vertex connectivity (or edge connectivity), which would be the obvious approach. Also, nobody could point out a Menger-type theorem. So yes, I think that this is a research level question, possibly with a simple answer or not.
someone
CC BY-SA 3.0
2011-12-13T21:35:56.103Z
Then that history should go *in the question*. Questions here should include their motivation and background as part of the question text. You don't win any points by making the community drag it out of you.
Josephine Moeller
CC BY-SA 3.0
2011-12-14T06:06:19.470Z
I don't know why people sometimes assume a question is homework without thinking about it first. I think you should not declare something homework unless at least you know how to solve it.
domotorp
CC BY-SA 3.0
2011-12-14T10:28:34.693Z
In case it is not obvious, the problem here is that $a$ and $b$ are part of the input.  Exhaustive search of the $a$ and $b$ conditions will therefore take time that is not polynomial in the input size.  The question is asking: can one do better than exhaustive search?
András Salamon
CC BY-SA 3.0
2011-12-14T11:12:34.200Z
@domotorp: people are usually asking if it is a homework, not claiming. It is hard to judge if a question is homework- *level* or not when the question does not contain background/motivation.
Kaveh
CC BY-SA 3.0
2011-12-14T18:36:34.833Z
@Kaveh: But I agree with domotorp that one should think about whether the question is easy enough to be homework before declaring it so.
Suresh Venkat
CC BY-SA 3.0
2011-12-14T20:31:18.877Z
My apologies for jumping the gun in asking whether the question was a homework question but it was partly because I misunderstood the question and thought it was easy. It happens, and I don't think one should get too worked up about this unless it becomes a major trend. It would help if people used their real names.
Chandra Chekuri
CC BY-SA 3.0
2011-12-14T22:51:32.893Z
I understand that my question could be misinterpreted as homework because of several reasons, but now we should move on. Actually, with the comment of Chandra Chekuri I got some hope that perhaps the question may have a simple answer...
someone
<ds.algorithms><graph-theory><graph-algorithms>
Connectivity of graphs by edge and vertex removal
someone
# Connectivity of graphs by edge and vertex removal

(Asked by: username_0 on 2011-12-13)

Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the standard definition, is $(k-1,0)$-connected, according to the new definition. Is there a polynomial-time algorithm to decide if $G$ is $(a,b)$-connected? Here I consider that the input is $G$, $a$ and $b$.

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Homework problem?  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_2**: ps: it would help if you provide some background and motivation for the question if you think the question is in cstheory's scope.  
> **username_0**: I came to this question during a talk of Janez Zerovnik about connectivity of networks about 2/3 years. To be honest, I do not remember the details. Since then, I have asked about 4 researchers and nobody saw how to reduce it to vertex connectivity (or edge connectivity), which would be the obvious approach. Also, nobody could point out a Menger-type theorem. So yes, I think that this is a research level question, possibly with a simple answer or not.  
> **username_3**: Then that history should go *in the question*. Questions here should include their motivation and background as part of the question text. You don't win any points by making the community drag it out of you.  
> **username_4**: I don't know why people sometimes assume a question is homework without thinking about it first. I think you should not declare something homework unless at least you know how to solve it.  
> **username_5**: In case it is not obvious, the problem here is that $a$ and $b$ are part of the input.  Exhaustive search of the $a$ and $b$ conditions will therefore take time that is not polynomial in the input size.  The question is asking: can one do better than exhaustive search?  
> **username_2**: @domotorp: people are usually asking if it is a homework, not claiming. It is hard to judge if a question is homework- *level* or not when the question does not contain background/motivation.  
> **username_6**: @Kaveh: But I agree with domotorp that one should think about whether the question is easy enough to be homework before declaring it so.  
> **username_1**: My apologies for jumping the gun in asking whether the question was a homework question but it was partly because I misunderstood the question and thought it was easy. It happens, and I don't think one should get too worked up about this unless it becomes a major trend. It would help if people used their real names.  
> **username_0**: I understand that my question could be misinterpreted as homework because of several reasons, but now we should move on. Actually, with the comment of Chandra Chekuri I got some hope that perhaps the question may have a simple answer...  

---

## 1 answers

### Answer by username_1 on 2011-12-14. Score: 8 | Accepted answer

This is an edited version of a previous "answer" which incorrectly claimed a polynomial-time algorithm for the problem. What I write below is a connection to an existing problem which suggests that the problem is difficult.

Let $s,t$ be two nodes in $G$ and we want to check if they are $(a,b)$-connected. That is removing any $a$ nodes and any $b$ edges should not disconnect $s$ and $t$. Another way to look at it as follows: what is the minimum number of nodes that we need to remove to reduce the edge-connectivity between $s$ and $t$ to $b$? These type of problems have been studied under the name multi-route cuts and they are dual to multi-route flows. Various approximation results have been shown though many basic problems are not yet resolved. A result of interest is the following. Suppose each edge has a cost $c(e)$ and we wish to remove the minimum-cost set of edges to reduce the edge-connectivity between $s$ and $t$ to $b$; then this problem is NP-Hard when $b$ is part of the input. This result is in the paper by Barman and Chawla: <http://arxiv.org/abs/0908.0350>

Two papers that will appear in upcoming SODA 2012 are on multi-route cuts which have further results on the topic. The one by Chuzhoy etal has hardness results for some variants.

> **Comments:**
> **username_1**: The Chuzhoy etal paper is now available on the ArXiv: http://arxiv.org/abs/1112.3611  

---

