GATE CS 2005 Q58 — Undecidability

To determine the complexity of the two problems, we analyze the time complexity of solving them on an undirected graph $G(V, E)$ with $n = |V|$ vertices and $m = |E|$ edges.

1. Analysis of Problem $\beta$

Problem: Does $G$ have an independent set of size $5$?

• The size of the independent set is a fixed constant, $k = 5$.
• The number of candidate subsets of vertices of size $5$ is given by the binomial coefficient: $$\binom{n}{5} = \frac{n(n-1)(n-2)(n-3)(n-4)}{120} = O(n^5)$$
• For each subset of size $5$, we can verify if it forms an independent set by checking if there are any edges between the $\binom{5}{2} = 10$ pairs of vertices. This verification takes $O(1)$ constant time.
• Thus, the total time complexity to find if such an independent set exists is $O(n^5)$, which is polynomial in terms of the input size.

Therefore, $\beta$ is in P.

2. Analysis of Problem $\alpha$

Problem: Does $G$ have an independent set of size $n - 4$?

• Recall the fundamental graph theory property: A subset of vertices $I \subseteq V$ is an independent set of $G$ if and only if its complement $V \setminus I$ is a vertex cover of $G$.
• If $G$ has an independent set of size $n - 4$, then the remaining $n - (n - 4) = 4$ vertices must form a vertex cover of $G$.
• Thus, the problem is equivalent to: Does $G$ have a vertex cover of size $4$?
• Since the size of the vertex cover is a fixed constant ($k = 4$), we can check all possible subsets of size $4$: $$\binom{n}{4} = O(n^4)$$
• For each subset of size $4$, we can verify if it covers all $m$ edges in $O(m)$ time.
• The total time complexity is $O(n^4 \cdot m)$, which is polynomial in terms of the input size.

Therefore, $\alpha$ is in P.

Conclusion

Since both problems can be solved in polynomial time, both $\alpha$ and $\beta$ are in class P.