Please when answering the question Put A B C as i have poseted the question up b
ID: 3884066 • Letter: P
Question
Please when answering the question Put A B C as i have poseted the question up before but the person never stated when their answer started and finished so i could not follow and I am unable to answer this question and been stuck on it for the last 3 days. Thank you :)
(A search problem.) An independent set consisting of exactly 6 vertices is required
for an input graph with n vertices. One possible (naive) algorithm for this search
problem rst iterates through all possible choices of 6 vertices of the graph. At each
choice of 6 vertices, the algorithm will then iterate through all pairs of the currently
selected 6 vertices and execute some kind of easy test.
(a) What is an independent set of vertices?
(b) In the worst case, how many times will some kind of easy test" be executed?
Show your calculations.
(c) Deduce what the easy test is doing.
(d) Is the time complexity of this exhaustive search algorithm in O(2n)? Explain.
Hint
Think about the counting of the first part of the algorithm with k = 6.
Then, how would you count for the second part? Putting it all together to answer part b.
apply knowledge from graphs, counting, and big O complexity.
Explanation / Answer
a-In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two
b-In the worst case, how many times will some kind of easy test" be executed 9 times