Instance: Collection C of subsets of a finite set S, positive integer K <= |S| * |C|, |S| = O(n) and |C| = O(n). For each subset c_i in C, we can choose some items in c_i to delete.
Question: Is there a way to remove at most K items from C such that after removal all resulting sets in C are distinct. For example, let S={1,2,...n}, C={c_1={1,2,4}, c_2={1,2,4}, c_3={2,4}} and K = 1. We can remove {2} from c_1 and the resulting sets are all distinct.

这个问题有什么高效的算法没有？ 抑或有人能给出一个np-complete的证明么？

• 顶！ (0) LIANGLIANG 2008-11-14 17:10:20
• 帮顶。。。牛人进来看看这个题目把。。。 (0) rruucc 2008-11-14 17:11:03
• 恩。。。我也来顶一下 (0) atlas_of_rruucc 2008-11-14 17:11:50
• 哇。。。rruucc的老牛集体现身！！！晚辈在此Orz了。。。。 (507) hanjialong 2008-11-15 18:17:20