gogateiiit's blog

Select maximum size subset from given numbers in array
By gogateiiit, history, 7 years ago, In English

Can anyone help me solve below problem?

Given an array with N numbers and given list of pair of integers u and v where each entry is two indices which cannot be together in chosen subset.Tell maximum possible size of such subset.

Don't worry about constraints tell your best solution.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maximum independent set. Polynomial (even linear) in some graphs.

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

    Thanks AlexandruValeanu for the reference,Original problem which I simplified to above problem was given array with N numbers find subset such that product of any two numbers in subset is not cube. 1<=N<=100 and number in 1<=array<=1000000 and 1 is cube. Any thoughts on how to solve it.

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

      I think it's a bipartite graph, so Max independent set problem can be solved by creating the flow network and getting the max flow, so the answer to the problem is:

      Ans = TotalNodesNumber - MaxFlow

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

        Can subset contain a cube? If it is so final graph can contain one clique of cubes in addition to bipartite part.

        → Reply