I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is polynomially bounded, i.e $|y| < p(|x|)$. In this case I guess that $|x| \text{~} n^2$ but I am not sure about $|y|$ .

Note - Definition For a given graph $G(V, E)$ each edge $E_{ij}$ has a $p_{ij}$-probability of being reliable and $(1 - p_{ij})$ probability of failure. Considering that each edge fails independently and nodes are perfectly reliable, the function

$Rel(G)$ = $Pr[$ for each pair of nodes $x_{i}$ and $x_{j}$ there exists at least one reliable path between them $]$

is called all-terminal connectivity (or reliability) function of the network.

  • 2
    $\begingroup$ 1. you should define the problem or link to a definition. 2. This smells like homework; if not, can you clarify where it comes from ? $\endgroup$ Oct 5 '10 at 21:33
  • $\begingroup$ @Suresh The fact is that finding "all-terminal connectivity polynomial" is known to be a NP-hard problem. What I want to proof here is that it is also hard to check whether a given solution is correct or not (what would make this problem hard to check and hard to find)...don't know if it is enough clear $\endgroup$
    – beca
    Oct 5 '10 at 21:50
  • 2
    $\begingroup$ then at the very least please define the problem in the question. $\endgroup$ Oct 5 '10 at 22:59
  • $\begingroup$ I have never heard of “all-terminal connectivity polynomial.” What is it? In other words, as Suresh said, please define the problem. $\endgroup$ Oct 6 '10 at 11:37
  • 2
    $\begingroup$ 1. I'd recommend you add the reference to the #P-completeness into the question, as well as the related paper, just so a reader has the full background. 2. While this is not a formal statement, it seems to me that it would be highly unlikely for a #P-complete problem to have a short proof. $\endgroup$ Oct 6 '10 at 20:38

I'll convert my comment to an answer.

The problem of computing the Rel(G) is #P-Complete (see this paper by Karger), and there's also an FPRAS for 1-Rel(G) (also in the Karger paper). Note that if you could verify whether Rel(G) was less than any fixed number $k$, then you could binary search for an approximate solution for Rel(G) that would run in P-time, which seems a little unlikely.


Your Answer

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