Due on 8 October 2004 at noon.

CSE 591 Assignment Two

1. Consider the all-terminal reliability of a graph G that has no loops and no multiple edges. Form a complete graph G' from G by adding an edge {x,y} having nonzero probability epsilon whenever x and y are NOT adjacent in G. Prove the following: if you can calculate the all-terminal reliability of G' in time which is polynomial in the size of G, then you can calculate the all-terminal reliability of G in time which is polynomial in the size of G. Hint: You get to choose epsilon. Warning: epsilon is rational, and its denominator can't be too large or it will be bigger than polynomial in the size of G.
2. Show that all-terminal reliability of bipartite graphs is #P-complete. (Assume that all-terminal reliability of general graphs is #P-complete.) Hint: use a reliability-preserving transformation.
3. Consider factoring for all-terminal reliability. Prove that the number of factoring steps never exceeds the number of spanning trees, provided that you never factor on a bridge or a loop.
4. A graph L(n,m) is defined as follows whenever n-1 <= m <= n(n-1)/2.
   • if m = n(n-1)/2, then L(n,m) is a complete graph;
   • else if m > (n-1)(n-2)/2, L(n,m) is obtained by adding a new vertex adjacent to ANY m - (n-1)(n-2)/2 vertices of L(n-1,(n-1)(n-2)/2);
   • else L(n,m) is obtained by adding a new vertex adjacent to ANY ONE vertex of L(n-1,m-1).
   (Aside: Any such graph is conjectured to have the lowest all-terminal reliability of any connected graph without loops or multiple edges, and having n vertices and m edges when every edge operates with the same probability. But that's not the question here.) Devise an EFFICIENT algorithm for computing the all-terminal reliability of L(n,m) when all edges operate with probability p.
5. Implement your algorithm for question (4) to calculate the N_i values (number of connected subgraphs with exactly i edges), and tell me exactly what the coefficients are for all cases with n = 3,4,5,6,7.
6. THIS IS A BONUS QUESTION, worth a few marks. In lectures, it was stated that factoring for all-terminal reliability on complete graphs, when you never factor on a loop or a bridge, and you always do parallel but never do degree-2 reductions, takes (n-1)!-1 factoring steps. Can you prove this is an upper bound? Hint 1: deletion/contraction? Hint 2: in factoring, if you know the reliability for G and for (G contract e), you can compute the reliability of (G delete e).

Email me if you have tried to figure out what to do, but have questions that you need answered.