Can this problem be solved in polynomial time?

Правка en2, от quinoa, 2021-05-18 19:08:00

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский quinoa 2021-05-18 19:08:00 66 Tiny change: 'I have N elements ' -> 'I have $N$ elements ' (published)
en1 Английский quinoa 2021-05-18 19:03:02 779 Initial revision (saved to drafts)