求贪心算法求解图最大独立集基数的递推关系及时间复杂度

算法伪代码（中文） #

def 最大独立集(G):
    max_node = G中度数最大的节点
    degree01 = G中度数为0或1的节点列表

    if G的节点数 == 0:
        return 0

    if len(degree01) != 0:
        node = degree01[0]
        return 1 + 最大独立集(G移除node及其邻居节点后的子图)

    if len(degree01)==0 且 max_node.degree > 2:
        v_inc = 1 + 最大独立集(G移除max_node及其邻居节点后的子图)
        v_exc = 最大独立集(G移除max_node后的子图)
        return max(v_inc, v_exc)

    if len(degree01) == 0 且 max_node.degree == 2:
        connected_components = G的所有连通分量列表
        sum = 0
        for component in connected_components:
            sum = sum + floor(component的节点数 / 2)
        return sum

算法基准情况 #

基准情况为图为空，或图中仅含度数为2的节点（此时直接按连通分量节点数的向下取半求和计算结果）。

时间复杂度分析问题 #

我尝试分析该算法的时间复杂度，但无法确定正确的递推关系T(n)（其中n为图的节点总数）。设n_i为图G中度数为i的节点数，针对最多包含度数4节点的图（此时n = n₀ + n₁ + n₂ + n₃ + n₄），我尝试写出了递推关系，但不确定其正确性，也不知道如何基于这些递推关系推导最终的时间复杂度。

我尝试写出的递推关系 #

• 当图中存在度数为0或1的节点时：每次递归至少移除1个节点（度数0节点仅移除自身；度数1节点移除自身及其邻居），递推关系为 T(n) = T(n - k) + O(1)，其中k≥1
• 当最大度节点度数为4时：选择包含该节点的分支会移除1个度数4节点+4个邻居（共5个节点），不包含该节点的分支仅移除该节点，递推关系为 T(n) = T(n-5) + T(n-1) + O(1)
• 当最大度节点度数为3时：选择包含该节点的分支会移除1个度数3节点+3个邻居（共4个节点），不包含该节点的分支仅移除该节点，递推关系为 T(n) = T(n-4) + T(n-1) + O(1)
• 当所有节点度数为2时：直接遍历连通分量计算结果，时间复杂度为O(n)

内容的提问来源于stack exchange，提问作者HHQ