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

  • 1
    $\begingroup$ Homework problem? $\endgroup$ Dec 13 '11 at 17:23
  • 6
    $\begingroup$ 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. $\endgroup$
    – someone
    Dec 13 '11 at 18:30
  • 7
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Dec 14 '11 at 6:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Dec 14 '11 at 11:12
  • 2
    $\begingroup$ 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... $\endgroup$
    – someone
    Dec 14 '11 at 22:51

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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