[Solved]: Is finding if a graph has k isolated nodes a NP-Complete problem?

Problem Detail: 

I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem:

Prove that the following problem is NP-Complete. Given a set of T transactions: $T = \{t_1,t_2,\dots,t_m\}$ where each transaction $t_i$ is a pair of banks $(b_{i1},b_{i2})$. Find if, given an integer value k, there is a group of k banks that doesn't perform any of the given T transactions.

I was thinking to proceed this way:

1. Input complete graph with all the Banks: $G=(B,E)$
2. Subtract to E the T set, I obtain a new graph, $G'=(B,E\setminus T)$
3. Find if there's an existing k-clique in $G'$

Is there any more effective way to solve this problem?

Asked By : Vektor88

Answered By : David Richerby

No, determining whether a graph has $k$ isolated vertices is not¹ NP-complete. Just count the number of isolated vertices and compare against $k$. This can be done deterministically in linear time (linear in the size of the graph's description; possibly quadratic in the number of vertices).

¹ Unless P=NP and, even then, it might not be NP-complete.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30132