Analysis and Synthesis of Reliable Networks

Home page for Dr. Wendy Myrvold
Publications for Dr. Wendy Myrvold
Department of Computer Science
University of Victoria

Contents

The Network Model
Analysis- Progress and Proposed Research
1. Cutsets
2. Spanning Trees and Trees with a few Extra Edges
Synthesis- Progress and Proposed Research

The Network Model

A probabilistic graph is used to model a communications network. The vertices of the graph represent communication centers and the edges represent communication links. We wish to study the effect on the network of random component failure. Component failures are assumed to be statistically independent. An argument against using a more complicated model for a network is that even for this simple model, most of the associated reliability problems are #P-complete (it is not likely that they are solvable in polynomial time).

The all-terminal reliability of a network is the probability that all the communication centers can communicate with each other. Under this model, a network is operational if the associated graph is connected. Since the probability of component failure is generally not known, it is typically reasonable to assume that components operate with equal probability p. This research is focussed exclusively on the all-terminal reliability problem. Colbourn's monograph provides an excellent survey of reliability results up to 1987.
Go to TOP.

Analysis- Progress and Proposed Research

One tactic for designing a reliable network is to construct possible network topologies and then to compare their reliabilities. One objective of this research is to provide fast, and effective tools for network analysis to facilitate this process. Many of the problems studied involve significant open problems in the area of graph algorithms.
Go to TOP.

Cutsets

The reliability of a network is a function of the numbers of cutsets that a graph has of each size. Colbourn and Ramanathan devised the first polynomial time algorithm for counting the cutsets of size at most lambda + k where lambda is the minimum cutsize and k is a constant. A new algorithm with faster asymptotic complexity than that of Colbourn and Ramanathan has been developed with the aid of my graduate student, Kim Cheung. This research suggests that generalizing the algorithm of Ball and Provan for counting minimum cutsets is a promising avenue for further improvement.
Go to TOP.

Spanning Trees and Trees with a few Extra Edges

The reliability of a network can also be expressed as a function of the number of connected spanning subgraphs that a graph has of each size. Liu and Chow designed a polynomial time algorithm for counting the number of spanning subgraphs of a planar graph consisting of a tree plus at most some constant number of edges. We have simplified the proofs in their paper and have also suggested ways of speeding up their algorithm. The next step is to consider graphs that are close to being planar.

For graphs that are not planar, no polynomial time algorithm is known for counting the connected spanning subgraphs which consist of a spanning tree plus a small number of additional edges. An open problem is whether this counting question is #P-complete. For these graphs, we have proposed a Monte Carlo algorithm for estimating the number of connected spanning subgraphs which are a tree plus a small number of additional edges. An offshoot of this work was the development (with Colbourn and Neufeld) of a fast algorithm for generating a random spanning tree of a graph. This algorithm also permits solution of the more general problem of unranking a spanning arborescence of a directed graph.
Go to TOP.

Synthesis- Progress and Proposed Research

In general, when comparing the reliability of two networks, it is essential to know the component operation probability. However, for particular numbers of communication centers and links, there are networks which are most reliable regardless of the operation probability of the links. A network is uniformly-most reliable if the probability that it is operational is at least as good as the probability that any other graph with the same order and size is operational, regardless of the probability of component failure. Obviously, uniformly-most reliable networks would be of particular interest to a network designer.

Our second objective is to completely characterize uniformly-most reliable networks when they exist. A first step is to establish various traits of these networks to narrow down the search space. The ultimate goal is to be able to provide an efficient construction which given the number of communication centers and links would output the uniformly-most reliable network if it exists, or the best network for the estimated component operation probability if it does not exist.
Go to TOP.

Cutsets

A necessary condition for uniform optimality is that the edge connectivity is maximized. In addition, the number of minimum cuts must be minimized. Certain circulants have been proposed as a network topology because they are nice in this regard. However, we have shown (with Nadon and von Schellwitz) that within a large subclass of 3-regular graphs satisfying these conditions, circulants are in fact the worst graphs you could select. This work classifies the almost minimum cuts (those of size equal to the minimum plus one) in quasi-prisms (a subclass of 3-regular graphs which includes cycle permutation graphs and generalized Petersen graphs). Our next step is to generalize these results to encompass all 3-regular graphs, or to consider special classes of 4-regular graphs. Ultimately, the goal is to obtain results that are applicable to all graphs.
Go to TOP.

Spanning Trees

It is easy to show that a uniformly-most reliable network must maximize the number of spanning trees. Futhermore, the question of which graphs on n vertices and m edges have the maximum number of spanning trees is interesting in its own right. We examine the family of graphs whose complements are a union of paths and cycles (with Gilbert) and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we obtain a simple proof of a result of Kel'mans- that evening out path lengths increases the number of spanning trees in the complement graph. We provide a similiar characterization for cycles. The theorems we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. This result was also obtained earlier by Petingi in his Ph. D. thesis (a paper is in preparation with C. Suffel and F. Boesch) and they also show (except for a few cases) that the best graphs are almost regular. We are working together to finish off this proof.

The next step is to consider the families of almost complete graphs where the vertices in the complement are of degree two or degree three. We first plan to examine small cases with the aid of the computer before formulating conjectures regarding the optimal graphs.

There is also potential for future research in the case that the graphs considered are fairly sparse. The graphs with the most spanning trees are known for up to n+3 edges (n is the number of vertices). Our approach to extending these results is to study how to subdivide a 3-regular graph some fixed number of times in order to maximize the number of spanning trees.

It seems apparent that a graph maximizing the number of spanning trees must have vertex degrees as regular as possible. This ``obvious'' condition seems very difficult to prove for the general case even though all known optimal examples have this property. A long term goal is to develop tools for showing that almost regularity is a requirement. This may be approached either as an optimization question (considering the eigenvalues of the Kirchoff matrix) or by producing spanning tree increasing operations which enable us to convert any graph which is not almost regular in its degrees to an almost regular one with more trees.
Go to TOP.

General Results

Boesch conjectured that uniformly-most reliable networks always exist. We found an infinite family of counterexamples to this conjecture in 1991 but later realized that this result had been proved (even before Boesch made his conjecture) by Kel'mans in 1981. Next, we showed (with Colbourn and Harms) that reliability polynomials can ``cross twice''. Or in other words, that it is possible to find two graphs G and H so that that G is more reliable both for small and large component operation probabilities, yet H is more reliable in the intermediate ranges.

It is possible for nonisomorphic graphs to have the same reliability polynomials, that is, they are reliability-equivalent. We have characterized theta-graphs (a theta-graph is composed of a cycle and a path which connects two vertices on the cycle) which are reliability equivalent.

Some general questions that we intend to investigate further are the relationships between various graph parameters such as girth and diameter to the reliability. The work with Nadon indicates that girth is an important parameter for 3-regular graphs when considering the small cutsets. Spurred by this research, we developed a backtrack program to find 3-regular cages (a cage is a graph of minimum order with a given girth). Brendan McKay has enhanced our code and added some isomorphism screening. We have been able to discover some new cages with the resulting program (these still need to be verified but we suspect they are correct).

Revision date: July 8, 1996.