生成树问题和支配集问题在网络中有着广泛的应用，其中最经典的是最小生成树问题、最小Steiner树问题以及最小支配集问题。 本文讨论了与这两类问题相关并有实际应用背景的若干问题，其中与生成树问题有关的问题有：允许顶点重复的巡路问题：信息交换共享问题；点边带权的最小生成树问题。而与支配集问题有关的问题有：C强支配集问题和完全支配集问题。 在本文中，我们首先给出这些问题的形式化定义，然后讨论了这些优化问题的复杂性，这些问题除一部分是多项式可解外其余大部分被证明是NP难的，就是说在P≠NP的假设下，不存在可解的多项式时间算法。另外，我们对其中的一些NP难问题给出了近似算法和近似度分析，这些近似算法分别基于最小生成树问题、最小Steiner树问题以及多重集合覆盖问题而得。