quinoa's blog

Can this problem be solved in polynomial time?
By quinoa, history, 4 years ago, In English

I have $$$N$$$ elements and I want to maximize the number of elements that can be selected given to some constraints of the type “you can take at most 1 element from this subset of the elements”.

Example

I have 10 elements (labeled 1 through 10) with constraints:

  • You can pick at most 1 element from the set { 3, 4 }
  • You can pick at most 1 element from the set { 2, 5, 6, 9 }
  • You can pick at most 1 element from the set { 1, 5, 7 }

An optimal solution is selecting elements { 1, 2, 3, 8, 10 }. I found this solution by writing the exponential solution.

I first thought I could reduce it to a maximum matching or flow problem but I failed to do so. Is it a known problem and can it be solved in polynomial time?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

The short answer is I cannot be sure, but after some thought:

If I formulate this problem as a graph problem, I add a node for each number, and an edge between each pair of elements which exist in a common subset. The problem then seems to be that of finding the maximum independent set for each connected component of the graph — this is strongly NP-hard, according to wikipedia.

So my instinct is that it cannot be solved in polynomial time, but it is plausible that I have formulated this incorrectly and someone better than me will wow us.

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

    And on the other hand if you have a graph you can for each edge (a, b) make a set {a, b} so these problems are equivalent.

    → Reply