# Connectivity of graphs by edge and vertex removal

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

• Homework problem? Dec 13 '11 at 17:23
• 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. Dec 13 '11 at 18:30
• 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. Dec 14 '11 at 6:06
• @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. Dec 14 '11 at 11:12
• 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... Dec 14 '11 at 22:51

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