Applications of Restrictive Cutsets and Topological CROSS's for

Minimum Total Load

 

 

 

ABSTRACT

 

We present some results of our continued study for efficiently finding  a Minimum Total Load of a load network using what we call Restrictive Cutsets and Topological CROSS(j)'s by showing that the set of all Restrictive Cutsets is the same as the set of all CROSS(j)'s for all possible topological orderings of nodes of the network whether the network has only one topological ordering of nodes or many of them.

We further present an efficient strategy of ordering topologically equivalent nodes in the case of multiple topological orderings in effectively ruling out all suboptimal orderings among these equivalent nodes.

 

 

I.    INTRODUCTION     

 

The usual cutsets in the flow network have been found very useful  for finding the maximum flow in flow networks  which are acyclic weighted digraphs with a unique Source node and a unique Sink node where edge weights are capacities (upper bounds) that cannot be exceeded (1,2,3,4).

 

In our previous studies (5,6,7), we changed the meaning of edge weights from this usual capacity (upper bound) to some kind of load (lower bound) that must be fulfilled instead. And, we call the resulting network a Load Network. There are some practical applications of this kind of networks. One prime example is an acyclic computer program interval digraph that can be used in software testing. In such a case, the edge weights may represent a minimum number of times a particular block of the software has to be executed in meeting a certain overall testing thoroughness criterion.

Naturally, in these load networks, a minimum total load is being sought instead of a maximum flow as in the case of the flow network.

 

 

II.    RESTRICTIVE CUTSETS AND TOPOLOGICAL CROSS(J)

 

A.        Usefulness of Restrictive Cutsets.

 

While the usual cutsets have been very useful for finding a maximum flow, they are not useful for this new problem. We devised to impose one additional restriction to the definition of cutsets. This extra restriction is that no two edges in the set are on any path of the network.

 

In Figure-1, two edges, (1,3) and (2,4) constitute a usual cutset. However, they are not a Restrictive Cutset simply because they are both on a path of the network although they certainly satisfy the other two conditions: disconnection and minimality.

On the other hand, two edges, (1,2) and (1,3) are both a usual cutset and our Restrictive Cutset.

 

We showed that the minimum total load of a load network and the Maximum Restrictive Cutset are equivalent (5,6). That is, the former is exactly the same as the sum of the weights of all edges in a maximum Restrictive Cutset. Hence, solving the Minimum Total Load Problem is the same as finding a maximum Restrictive Cutset.

 

A.        Equivalence of Restrictive Cutsets and Topological CROSS(j)'s

 

It is known that every acyclic connected digraph has at least one topological ordering of nodes. We showed that if a network has only one topological ordering there are exactly n-1 Restrictive Cutsets in the network where n is the total number of nodes in the network, We further showed that in such a case of exactly one topological ordering, all cutsets can be found in a linear time.

 

When a network has multiple topological orderings, there will be way more Restrictive Cutsets  than the total number of nodes in the network and we will show how to efficiently identify optimal ones by ruling out suboptimal ones. For this, we devised another structure called a Topological CROSS(j).

 

Definition-1: Topological CROSS(j)     (To be abbreviated just as CROSS())

            Given a topological ordering of nodes, unique or not, we will number all the

            nodes in the same ascending order as the given topological ordering. Then

        for each node j,  1<=j<n (n is the number of all nodes, and it is also the last

node number)  we define CROSS(j) to be the set of all edges of form (p,q)

of the network such that  p<=j and q>j.

 

Note that the departing node (p) of any edge in CROSS(j) must be preceding the node j (or it can be the node j itself) and the terminating node (q) must follow the node j.

 

For example, Figure-2 shows a unique topological ordering of the nodes of the network of Figure-1.  For this ordering we have the following three CROSS(j)'s

CROSS(1) = { (1,3), (1,2) }  with total load of 25.

CROSS(3) = { (1,2), (3,2), (3,4) } with total load of 15.

CROSS(2) = { (2,4), (3,4) }  with total load of 25.

 

We showed that when the network has only one topological ordering of nodes, there are exactly as many CROSS(j)'s as there are Restrictive Cutsets, namely, n-1 of them.

We also showed that in this case the set of all CROSS(j)'s and the set of all Restrictive Cutsets are equivalent and hence, CROSS(j)'s can be used to find Restrictive Cutsets.

 

Now, we will show that even when there are multiple topological orderings of nodes, the above-stated equivalence holds. The following two lemmas will establish this.

 

Lemma-1.  Every Restrictive Cutset is a CROSS(j) for some topological ordering.

 

Proof:

   Let C represent a Restrictive Cutset under consideration and assume that it has k>0

   edges.   These k edges are (m1, n1)

            (m2, n2 )

                 .

                 .

                 .

            (mk, nk )

   First, we note that since no two edges in C are on any path of the network, no

   terminating node of any edge in C can reach the departing node of any edge in C.

 

   We consider two groups of nodes of these k edges. The first group will consist of all

   departing nodes (m's) and the second group will consist of all terminating nodes

   (n's). Clearly, we can  topologically order nodes within each group as all the nodes of the   

   network have a topological ordering.  Next, we put two groups of nodes and order them

   together, preserving the ordering within each group, in such a way that all the nodes in

   the first group will precede all the nodes in the second group.

   Now, let the last node in the first group be node mj =  J 

   We claim that the Restrictive Cutset C under consideration is CROSS(J).

   Clearly, from the construction of  CROSS(J), every edge in C is in CROSS(J).

   Now we need to show that every edge in CROSS(J) is also in C.

   Assume to the contrary. That is, there is an edge (p,q), where p<=J, and q>J,

   in CROSS(J) but not in C.

   We note that any edge not in a Restrictive Cutset must be covered by at least one

   edge in the Restrictive Cutset by being on the same path together.

   Hence, this edge (p,q) and at least one edge in C must be on the same path.

   We call this edge in C  (ml, nl)     

   We have two cases to consider.

a.       (ml, nl) precedes (p,q)

b.      (p,q) precedes (ml, nl)

       Case-a implies that  nl <= p, which is a contradiction as p<=J and  J < nl.

       Case-b implies that  q <= ml, which is a contradiction as q>J and ml<J.

                        Q.E.D. 

 

Now, we prove the converse in the following lemma.

 

Lemma-2: A CROSS(j) for a given topological ordering is a Restrictive Cutset.

  

Proof:       

   A Restrictive Cutset must satisfy three conditions:

1.      Disconnection.

Removal of all edges in CROSS(j) will disconnect any node  i (<=j)

         from  every node k (>j) since any path connecting these two nodes must   

         contain an edge in CROSS(j).

         Hence, the Sink node will be disconnected from the Source node, in particular.

2.      Path Singularity.

Suppose that two edges, (m,n) and (p,q) of CROSS(j) were on the same path of

the network.  In this case, either  n<=p or q<=m.

But, we have m,p < n,q as the result of a topological ordering among these four

nodes, leading to a contradiction.

3.      Minimality

Suppose that an edge (p,q) in CROSS(j) were not needed to be removed for the desired disconnection between the Source and the Sink node.

We have p<=j<q.

Since the network is connected, there is a path from the Source to node p and another path from node q to the Sink. The first path contains only nodes <= p (<=j) and the second path contains only nodes >q. Hence, no edge on these two paths is in CROSS(j) as an edge (r,s) in CROSS(j) must be such that r<=j and s>j.

Therefore, not disconnecting this edge (p,q) would leave a path from the Source to the Sink. Q.E.D

 

 

III.    TOPOLOGICAL ORDERING SELECTION

                  

A.      Some definitions

 

Having shown that the set of all Restrictive Cutsets and the set of all CROSS(j)'s

for all possible topological orderings are equivalent, we will now present an efficient selection strategy to use in deciding an optimal ordering among nodes when there is no definite order among them, i.e., when the network presents multiple topological orderings.

We need some simplifying definitions, first.

  a.   In-sum of a node

It is the sum of all incoming edge weights of a given node

b.      Out-sum of a node

      It is the sum of all outgoing edge weights of a given node

c.       A More-in node

      It is a node whose In-sum is greater than its Out-sum.

d.      A More-out node

It is a node whose Out-sum is greater than its In-sum.

e.       A Balanced node

It is a node whose In-sum and Out-sum are the same.

f.       Topologically equivalent nodes

Two or more nodes with no definite ordering among them, i.e., any one

can precede all others.

 

B.      Ordering Selection Strategy

 

We present an efficient selection strategy to use in ordering topologically

equivalent nodes as a lemma.

 

Lemma-3: Whenever we come to two or more equivalent nodes during a       

                  topological ordering process, we will always select a More-out node

                  before any More-in nodes and Balanced nodes.

           However, a Balanced node may be selected at any time.

 

Proof:

      a.  Any CROSS (j) resulting from ordering all equivalent nodes will include  

           exactly either the In-sum or the Out-sum of every equivalent node on hand at

           any point in time.

      b.  On the other hand, all the edges connecting any preceding node (i.e., one

    preceding all equivalent nodes) to any following node (i.e., one following

    all equivalent nodes) will be included unaffected into every CROSS(j)

    resulting from ordering these equivalent nodes under consideration

      c.  Therefore, by selecting every More-out node before all More-in nodes, we

           can maximize the resulting sum as one CROSS(j) will include the higher of

           either the In-sum or the Out-sum of every equivalent node under consideration.

      d.  We claim that CROSS(j) for the More-out node j  that was being selected last

    has this maximized sum because all preceding equivalent More-out nodes and

    all following equivalent More-in nodes will have their respective higher sum

    included into this CROSS(j). Q.E.D.

     

As an illustration of Lemma-3, we consider the network of Figure-3 one of whose multiple topological orderings is given in Figure-4. This ordering is made as follows:

 

  1. After selecting node #1 first, we find three equivalent nodes, #2, #3, and #4.
  2. Of these three nodes, #2 and #3 are More-out while #4 is More-in.
  3. So, next either one of #2 or #3 must be selected and #2 is selected arbitrarily.
  4. Now,  node #5 becomes equivalent as well and it is More-out.
  5. So, next either one of #5 or #3 must be selected and #5 is selected arbitrarily.
  6. Next selection of node #3 is absolute as it is the only remaining More-out node.
  7. Next selection of node #4 is absolute as it is the only remaining equivalent node.
  8. Next, nodes #6 and #7 are equivalent. And, node #6 is More-in and node #7 is Balanced.

Although the choice between these two is arbitrary, we may select Balanced nodes first and in this case then #7 is selected before selecting #6.

  1. Next selection of the last node #8 is absolute.

 

We note that, among the three equivalent nodes, #2, #3, and #4, the node #3 happened to be the last More-out node that has been selected, and hence that CROSS(3)  has a total load which is 80 that is no less than that of any other equivalent node. Therefore, while CROSS(3) may represent  the maximum Restrictive Cutset the other two CROSS's cannot.

 

 

IV.             CONCLUSION

 

In this paper,  we extended  our early study result by showing that the set of all Restrictive Cutsets and the set of all CROSS(j)'s for all topological orderings of nodes are equivalent whether the network has only one topological ordering or more of them. We further demonstrated an efficient selection strategy to effectively rule out suboptimal orderings of equivalent nodes when the network has multiple topological orderings by selecting an ordering that can realize the larger of either the In-sum or the Out-sum of every equivalent node involved at any point in time without affecting an ordering among other nodes.

 

We firmly believe that the very conception of as well as the application of Restrictive Cutsets and Topological CROSS(j) itself  should be regarded as a contribution to the field of Computer Science in general and Algorithm Design in particular.

 

We plan to further our study in attempting to capture some critical restrictions (like the very existence of a topological ordering of nodes) inherent in our Minimum Total Load Problem that apparently reduces noticeably the complexity of what should be generally considered to be an Integer Programming Problem.

 

 

REFERENCES

 

1. Syslo, Maciej and Deo, Narsingh,  Discrete Optimization Algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1983, pp. 54-95.

2. Hu, T.C., Integer Programming and Network Flows,  Addison-Wesley,

Reading, Massachusetts, 1969, pp. 105-119.

3.   Lewis, Harry and Papadimitriou, C.H.,  Elements of the Theory of               

      Computation, Prentice Hall, Englewood Cliffs, New Jersey, 1998,

pp. 275-330.

4.   Papadimitriou, C.H. and  Steiglitz, Kenneth, Combinatorial

Optimization, Prentice Hall, Englewood  Cliffs, 1982, pp. 91-97, 117-124.

5. Koh, Hikyoo, Heuristic Elimination for Minimum Total Load in Load

      Network, Proceedings of Simulation and Modeling Conference,

      Pittsburgh,  PA, 1989, pp. 731-737.

6.   Koh, Hikyoo, Flow Network Reduction for Unique Topological Ordering,

ACM Computer Science Conference, Louiville, KY, 1989,  pp. 332-337.

7. Koh, Hikyoo, Restrictive Cutsets used for Solving Minimum Total Load Problem in Load Networks,  Paper Number 1.1.1, 1998 Korea-US Science and Technology

Symposium, Chicago, Illinois, April 1998.

 

 

 

 

 

FIGURES

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


              

 

 

 

 

 

 

 

 


"Bo Sun" <bo.sun@lamar.edu>;