This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Independent Set Problem”.
1. Which of the following refers to the set of non-adjacent vertices?
a) Independent set
b) Dominant set
c) Vertex cover set
d) Edge cover set
View Answer
Explanation: In a graph G with V vertices and E edges, there exists a set of vertices, in which no two vertices are adjacent. This set of non-adjacent vertices is called an independent set i.e. no two vertices share a common edge.
2. Which of the following refers to the independence number of a graph?
a) Smallest size of a maximal independent set
b) Largest size of a minimal independent set
c) Smallest size of a minimal independent set
d) Largest size of a maximal independent set
View Answer
Explanation: In a graph G=(V, E) a subset S is an independent set if no two vertices in the S are adjacent. The independence number of graph G is the cardinality of the largest size of an independent set of vertices.
3. Given below is the pseudocode of the independent set problem. Which of the following best suits the blank?
Independent (G = (V, E))
{
temp=true
for every {u, v} in the subset
{
check if they have any edge between them
if edge exist, then set ________________
}
If temp is true
correct result
else
incorrect
}a) temp to true and continue
b) temp to true and break
c) temp to false and break
d) temp to false and continue
View Answer
Explanation: The given pseudocode is for solving the independent set problem. First, initialize a temporary variable as true. Now, check that each pair of vertices belong to the set are adjacent or not, by checking if there exists any edge between them.
4. What is the maximal independent set for the graph given below?
a) {C, D, E, G}
b) {A, C, D, F}
c) {A, E, B, C}
d) {A, B, C, D}
View Answer
Explanation: The maximal independent set S of a graph G contains the set of vertices, such that no two vertices should be adjacent and no vertex can be further added to the set. If we start with vertex A, we can’t select vertex B. Select vertex C and D, hence we can’t select E. Now, select any vertex from F and G according to the given options. Hence, the set contains the vertex {A, C, D, F}.
5. In a graph, an independent set is maximal if no further vertex can be added to the stay independent.
a) True
b) False
View Answer
Explanation: In a given graph G=(V, E), an independent set of G is a subset S of the vertices present in the graph G, such that no two vertices of S are adjacent in G. Hence, a maximal independent set of graph G is a set where it is impossible to add another vertex and stay independent.
6. What is the independence number of the graph given below?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The independence number of the graph is given by the largest size of an independent set. If we start with vertex A, we can’t select vertex B. Select vertex C and vertex E. The maximal independent set of the graph will be {A, C, E}. Hence, the independence number of the graph is 3.
7. What is the size of the smallest maximal independent set of a chain of 7 nodes?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: In a graph G, a set of vertices is an independent set if there is no common edge between them. A maximal independent set of graph G is a set where it is impossible to add another vertex to make it independent. Here, we can select the 2nd, 5th and 7th node to get the smallest maximal independent set (1—2—3—4—5—6—7). Hence, the size of smallest maximal independent set of a chain of 7 nodes is 3.
8. The pseudocode for the independent set problem is given below. Which of the following gives the time complexity for it?
Independent (G = (V, E))
{
temp=true
for every {u, v} in the subset
{
check if they have any edge between them
if edge exists, then set temp as false and break
}
If temp is true
correct result
else
incorrect
}a) O(V + E)
b) O(V)
c) O(V log V)
d) O(V log E)
View Answer
Explanation: To check whether the given subset of vertices of a given graph is an independent set, we need to check that all the vertices present in the set are non-adjacent. This can be done by confirming that they don’t share any edge. This can be performed in polynomial time. Hence, the time complexity is O(V + E).
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Programming Books
- Check Design and Analysis of Algorithms Books
- Check Computer Science Books
- Practice Data Structure MCQ
- Practice Computer Science MCQs
