17

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

Community
  • 1
someone
  • 1,414
  • 12
  • 19
  • 1
    Homework problem? – Chandra Chekuri Dec 13 '11 at 17:23
  • 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 Dec 13 '11 at 17:57
  • 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 Dec 13 '11 at 17:58
  • 6
    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 Dec 13 '11 at 18:30
  • 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 Dec 13 '11 at 21:35
  • 7
    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 Dec 14 '11 at 06:06
  • 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 Dec 14 '11 at 10:28
  • 1
    @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 Dec 14 '11 at 11:12
  • @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 Dec 14 '11 at 18:36
  • 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. – Chandra Chekuri Dec 14 '11 at 20:31
  • 2
    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 Dec 14 '11 at 22:51

1 Answers1

8

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.

Chandra Chekuri
  • 6,999
  • 31
  • 39