难问题的部分分类 1 包装问题 包装问题主要有独立集问题和集合包装问题。 (1)独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗? (2)集合包装问题:给定 nnn 个元素的集合 UUU , UUU 的子集 S1,S2,...,SmS_1,S_2,...,S_mS1​,S2​,...,Sm​ 以及数 kkk , 问在这些子集中至少含有 kkk 个集合两两不相交? 2 覆盖问题 覆盖问题主要有顶点覆盖和集合覆盖问题。 (1)顶点覆盖:给定图G和数k,G是否包含大小为k的顶点覆盖? (2)集合覆盖:给定 n 个元素的集合U,U 的子集S1,...,SmS_1,...,S_mS1​,...,Sm​ 以及数 k,