PARALLEL INDEPENDENT SETS
Parallel Programming
Introduction: -
“As I proceed, I’d like to explain what an independent set is. Officially, an independent set S of a graph G = (V, E) is any subset of vertices S ⊆ V where no vertices in S are neighboring. One of the essential features of any successful parallel algorithm design is the ability to be effectively divided into a number of nearly similar basic algorithms that, when executed in parallel, provide an accurate problem output quickly.
Real Life Application: -
Parallel Independent is used to solve complex problems in a variety of engineering disciplines, not just computer science. A real-life example of how parallel independent sets are used in biotech engineering is DNA sequencing.
Algorithm: -
So now let’s move on to the algorithm part.
A parallel independent set can be computed using a randomized approach. The steps are as follows:
(1) Toss a coin for every node in parallel. Every node will get a head with a chance of 0.5 and a tail otherwise. If the coin comes up with the head, it will be added to the independent set. But, if it is a tail, it will be excluded from the set.
(2) According to the norm, no head will be close to another head, only to the tail. If the provided node as well as its adjacent are both heads, one of them must be modified to tail.
The pseudo-code for the parallel independent sets is as follows:
A more detailed pseudo-code for the parallel independent sets is as follows:
Example: -
So now let’s move on to the example part for the parallel independent set.
In this example, as we can see, no two vertices are adjacent to each other, as 4’s adjacent vertex is 2, and 2 is not in Set I. The next number we have is 7 and the adjacent vertex of 7 is 1, which is also not in Set I same goes for 3 and 6, as the adjacent vertices are 5 and 8, respectively, which are also not present in Set I.
So, now let’s see one more example to clarify our algorithm more clearly: -
In this example we can see that in the set I we have 3 in it which is a valid answer as it’s adjacent vertices 1 and 5 are not present in the set I. Next, we have is 4 which is also a valid answer as it’s adjacent vertex 2 is also not present in the set I. Next, we have is 6 which is not a valid answer as it’s adjacent vertex 8 is also present in set I. Only either of the two (6 and 8) should be present in the set I. After that only the set I will be called Parallel Independent set.
Work and Span: -
So, now let’s look into the work and span for this algorithm:
The Work would be:
W(n): -> n
The Span would be:
D(n): -> log n or 1
Interesting Fact: -
Do you what is the average number of vertices that end up in the independent set?
The answer for that would be ¼ n.
Conclusion: -
In this report, I investigated parallel independent sets as well as serial independent sets. I have defined what is independent sets, parallel independent set, given a real-world example, pseudo codes for parallel, demonstrated how to solve a parallel independent set problem using an algorithm, work and span for the algorithm and an interesting fact.
Acknowledgment: -
I am a Bennett University student in the Department of Computer Science and Engineering. I completed this research as part of a report for my High-Performance Computing class.”
REFERENCES: -
1- Maximal independent set — Wikipedia
2- Parallel Independent Set Algorithms for Sparse Graphs | Semantic Scholar
3- Mathematics | Independent Sets, Covering and Matching — GeeksforGeeks
4- A parallel algorithm for the independent set problem | IEEE Conference Publication | IEEE Xplore
5- Independent set (graph theory) — Wikipedia
6- https://people.csail.mit.edu/jshun/simple-analysis.pdf
7- https://algo2.iti.kit.edu/lamm/theses/tom_george.pdf
8- https://jgaa.info/accepted/2011/AsanoMulzerWang2011.15.5.pdf
9- https://link.springer.com/chapter/10.1007/3-540-60220-8_84
An example of real-life problem was referred from here
10- https://cs.stanford.edu/people/eroberts/courses/soco/projects/dna-computing/clique.htm
