Student: Daniel MacDonald
School: Seton Hall University, Mathematics and Computer Science Dept.
Email: macdondb [at] shu [dot] edu
Research Area(s): Graph Theory
Project Name: Generation of Shortest Paths and Minimal Cutsets
Faculty Advisor: Dr. Endre Boros, Professor of Operations Research at RUTCOR, Rutgers University

Project Description

The Problem we are working on arises in graph theory when we want to generate all the short paths from a unique source vertex s to a terminus t. "Short path" is being defined here as all s-t paths of length less than or equal to some L. Another problem that comes out of this one is finding ways of finding the minimal amount of edges to cut from the graph's edge set such that all short paths are blocked.

Approaching the problem

We are approaching this problem by looking at special classes of graphs, and trying to develop short path and minimal cutset algorithms for these.

One type of graph we are looking at is called the Hierarchical Communications web. You can view what this looks like here. A graph like this has a few interesting properties that make it nice to work with. First of all, it is a very realistic model. Because our problem has many applications (such as in communications, as the graph title suggests ;)), it would be ideal to work with as realistic a model as possible. It so happens that this model is also good to work with when coming up with cutsets.

Another special type of graph that we have looked at is called the seesaw graph. You can take a look at this type of graph here. This type of graph is particularly nice for notation. As you can see in the picture, each bottom vertex is labeled 0 through 4. You can then label the corresponding hump by labeling the first one a1, then a2, etc. So if you wanted to describe the path of length 4 from v0 to v4, you'd simply write "v0-v1-v2-v3-v4", or if you wanted to skip v0-v1 and instead follow that first hump, you could write "v0-a1-v1-v2-v3-v4". So you can list all paths like this, it is a very nice setup. There turns out to be 2k possible paths between v0 and vk. If you then list them, you can analyze the various structures of the paths, and try to see what you want to cut.

Ideas

For the second half of our project, we specifically looked at the Hierarchical Communications Web. The reason this is so is because of the application to the problem that we looked at.

Dr. Boros gave us a paper by Lawler, Lenstra, and Rinnooy Kan (1980) that talked about the maximal independence set problem. In the general case, this problem is NP-Complete. However, the paper mentions a specific subproblem that (if it could be solved in polynomial time), could be applied to problems that deal with maximal independence sets. The paper then goes through and explains this procedure, known as the "I È {j}" problem.

IÈ {j} and its importance

How does this problem help us? For the complete details, you should reference the paper that we have written on our project, located at the top and bottom of this page. The main idea was that if we were able to find some way of labeling the edges in our graph in a nice order, and come up with a good test for maximality, all we would really have to do is consider each edge in an increasing order, and eventually we would cover our entire edge set.

Testing for maximality

An independence set I is maximal if there exists no I' in the family of independence sets that is a strict superset of I. The term "maximal" fits nicely in our project, because often in mathematics it is nice to consider complementary problems. In our case, the notion of a maximal independence set is complementary to the notion of a minimal cutset.

The actual test for maximality occurs in the boolean function. Say you have a list of short paths that you would like to find the cuts to. Using the algorithm that we have developed based on the IÈ {j} problem, this is completely possible. Furthermore, it can be done in a systematic order, just considering j, then j+1, all the way up to n, if n is the number of edges in the graph. For each j, the short paths would be those whose first edge is j.

Say the edges on the path are {a,b,c,d},{a,b,c,e},{a,b,f,g}. We construct a boolean function based on these edges as follows: (aÚbÚcÚd)Ù(aÚbÚcÚe)Ù(aÚbÚfÚg).

Logically, this is what we are saying: We want to cut all paths listed. To do this, we can cut (a or b or c or d) and (a or...) and ... The result of this logic will be all minimal cutsets. It is the same as the boolean function. We have a boolean function, and if we were to distribute the terms, we would get each minimal cut as a conjunction of terms, each separated by a disjunction (because we have to cut this and this and... or cut this and...).

The Results

This webpage is really meant for the people that are not so math-inclined who are viewing this page to understand what our results are about. If you would like to see the formal paper in LaTeX, that is available here.

The powerpoint presentation that we gave at the end of the program is available here