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:
- Input complete graph with all the Banks: $G=(B,E)$
- Subtract to E the T set, I obtain a new graph, $G’=(B,Esetminus T)$
- 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 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). 1 Unless P=NP and, even then, it might not be NP-complete.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30132
