Is this problem NP?

Правка en1, от backo, 2016-07-13 16:18:47

Hello, recently I've come across a problem (not a competition task) and I'm wondering if there is an efficient solution to it. The task follows:

Given a structure like this [ (2,3), (1), (2,3,4) ] you can easily construct all possible combinations: (2,1,2),(2,1,3),(2,1,4),(3,1,2),(3,1,3),(3,1,4)

Now if you're given n tuples of length m, you need to group them in a way that minimizes the ammount of structures that you get as a result.

E.G. n=7,m=3 tuples: (5,3,10),(4,3,2),(0,4,7),(1,4,7),(5,3,2),(4,3,10),(5,2,9) can form groups [ (5,4),(3),(2,10) ], [ (5),(2),(9) ] and [ (0,1),(4),(7) ]

It kind of smells like set cover problem or something like that but I'm not sure.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский backo 2016-07-13 16:18:47 708 Initial revision (published)