psywoo's blog

By psywoo, history, 6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

It is NP-hard problem in general.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    any Proof for why is it NP — hard ?

    • »
      »
      »
      6 weeks 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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

cant this be solved using DSU?

answer: NO