Algorithm to find fewest number of tags that encompass all items?

Question

I'm thinking this might be NP-complete, but I'll ask anyway. Greedy algorithms don't seem to work in my head.

Given a set of items, each with 1 or more tags, I want to find the smallest set of tags that cover all the items.

Edit: See my "solution" here.

Answer 1

This is the Set Cover problem, which is NP-complete. Each tag defines a subset of your list of items, and you want to find the minimum number of subsets (tags) whose union equals the full list of items.