psywoo's blog

Largest Independent set of nodes problem
By psywoo, history, 3 years ago, In English

Problem : You are given a connected graph with N nodes and M edges, graph does not contain multiple edges and self loops. An independent set of nodes is the set in which no two nodes are connected to each other. You need to find the largest independent set.

Constraints : 3 <= N <= 1e5 and (N — 1) <= M <= 2e5

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It is NP-hard problem in general.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    any Proof for why is it NP — hard ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      page 12 of this

      NP hardness also noted in "Independent set (graph theory)" wikipedia article.

      → Reply