Ballista's blog

Non adjacent graph nodes maximum sum
By Ballista, history, 5 years ago, In English

Given a Graph $$$D$$$ of $$$N$$$ nodes, where each node $$$i$$$ has $$$C_i$$$ coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes(i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.

For a tree this is a famous DP on Tree problem ( solution for Tree version here: https://codeforces.me/blog/entry/20935 -> Problem 1 ). Can we extend the DP on trees logic to solve it for a general graph. If not how can should I approach it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's NP. Since we have an equivalence with maximum independent set.

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

    Is it NP even for a DAG?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +26 Vote: I do not like it

      Yes, because the edge directions are completely irrelevant here. Given any graph, you can direct its edges so that it becomes a DAG.

      → Reply