The main method used is a reduction to the maximum independent set problem.

Definition (Maximum Independent Set of Pairs (MISP)).

To obtain the minimal upper bound on the possible distinct outcomes set, a maximum independent set count problem would have to be solved for every node, as proved in Appendix A, and the maximum of the obtained values should be used as the upper bound.

Therefore, the maximum number of paths from node s to t that can be chosen together is equal to the size of the maximum independent set of this graph.

Note that the

maximum independent set and minimum vertex cover problems are complementary.

A

maximum independent set (mis) is a maximum cardinality subset of V such that there is no edge between any two vertices of it.

We show that the maximum nonoverlapping dense blocks problem is NP-complete by a reduction from the

maximum independent set problem on cubic planar graphs.

This algorithm finds a

maximum independent set B [subset or equal to] E of the overlap graph H = (E, I), reduces the overlap graph by removing from it the vertices in B and all edges incident to vertices in B, and then finds a

maximum independent set R [subset or equal to] E \ B in the remaining overlap graph H' = (E \ B, I').

An independent set in graph G = (V, E) is a subset V[prime] [element of] V such that, for every pair ([v.sub.i], [v.sub.j]) of vertices in V[prime], the edge [v.sub.i][V.sub.j] does not belong to E, and the

maximum independent set problem (IS) is to find a maximum size independent set.

introduced a constant approximation algorithm with the latency bounded by (23.R + [DELTA] - 18) [4] by building the aggregation tree with the help of

maximum independent set (MIS), where R denotes the network radius.

In the

MAXIMUM Independent Set problem (MIS), the input is a graph and the task is to find a largest independent set in this graph.

A solution to the NP-hard

maximum independent set problem is an independent set of maximum cardinality.