# Is finding if a graph has k isolated nodes a NP-Complete problem?

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?

• Your algorithm is looking for an "independent set", i.e. a set of nodes that don't have edges between them, but may have edges with nodes outside the set. Your introduction on the other hand talks about "isolated nodes", i.e. nodes that don't have any edges at all. The cited problem statement could be interpreted both ways (but the problem is only NP-complete for the "independent set" interpretation). Sep 19 '14 at 10:31
• @FrankW I managed to get an answer from the author of the problem and he told me that the "independent set" interpretation is the correct one. There are no banks besides the ones listed in T, and the goal is finding a group of k banks that don't perform any transaction between thems. The text was a bit misleading and prone to be misunderstood.. Sep 19 '14 at 17:47

No, determining whether a graph has $k$ isolated vertices is not1 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).
• @FrankW It's in L and maybe L$\neq$P. Sep 19 '14 at 12:34