1
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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). $\endgroup$
    – FrankW
    Sep 19 '14 at 10:31
  • $\begingroup$ @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.. $\endgroup$
    – Vektor88
    Sep 19 '14 at 17:47
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Why would it not be NP-complete, if P=NP? There are both yes and no instances and it definitely is in P. $\endgroup$
    – FrankW
    Sep 19 '14 at 12:32
  • 2
    $\begingroup$ @FrankW It's in L and maybe L$\neq$P. $\endgroup$ Sep 19 '14 at 12:34
  • $\begingroup$ But still every problem in NP(=P) can be trivially reduced to it in polynomial time. So it's NP-complete. (It may not be P-complete, since a different type of reduction is used for that.) $\endgroup$
    – FrankW
    Sep 19 '14 at 12:46
  • 1
    $\begingroup$ NP-completeness is often specified in terms of logspace reductions rather than polynomial time. If P=NP, it wouldn't make sense to define completeness for the class by different reductions depending on whether you call the class P or NP. $\endgroup$ Sep 19 '14 at 12:56
  • $\begingroup$ I accept this answer because my question was "is finding isolated nodes a np-complete problem?" and it's not, but I gave a wrong interpretation to the problem and the correct goal was to find a k-Independent-Set, as @FrankW suggested. $\endgroup$
    – Vektor88
    Sep 20 '14 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.