如何证明下面的问题是NP-complete

img


给定条件 : A graph G(V，E) and an Integer T.
问题 Does the graph contain a subset V' of V of size T or greater such that for each edge (u,v) 从属于E, at most one of u and v are in V'?(such a set is called independent set)

基于Monster 组和GPT的调写：

  • 该问题是经典的独立集问题（Independent Set Problem），其NP完备性已经被证明。
  • 首先，可以证明该问题属于NP类。给定一个独立集V'，可以在多项式时间内验证它是否符合要求。具体来说，可以检查每个边，确保在该边的两个端点中最多只有一个在V'中。
  • 接下来，需要证明该问题是NP难问题。为此，我们将使用图的3-SAT问题（3-Satisfiability Problem）的约减，该问题已知是NP完全的。在图的3-SAT问题中，我们有一个布尔公式，其中每个子句最多包含3个变量。问题是找到这些变量的一种赋值，使得公式成立。
  • 可以将每个变量表示为图G中的一个顶点，每个子句表示为一个大小为3的集合，其中每个元素表示为一个边。可以将图G中的每个顶点与每个子句中的边相连。这将生成一个新的图G'。
  • 现在，将证明以下结论：图G有一个大小为T或更大的独立集V'，当且仅当原始3-SAT问题有解。

证明：

  • 如果原始3-SAT问题有解，则可以将每个变量赋值给G中的相应顶点，使得每个子句都得到满足。这意味着在图G'中，可以选择每个子句中的至少一个边，而不选择其余边。这将生成一个大小为T或更大的独立集V'，满足每个子句中的至少一个边都被选择，因为每个子句中的边都与其关联的三个变量中的至少一个相关联的顶点相连。此外，由于每个子句至少包含一个变量，因此独立集中至少包含一个相应的顶点。因此，该独立集符合条件。
  • 如果图G有大小为T或更大的独立集V'，则可以将每个变量设置为与其相关联的顶点是否在V'中的布尔值。由于V'是独立集，因此不存在两个相邻的顶点都在V'中的情况。这意味着每个子句中至少有一个变量的值为真，否则该子句中的三个变量中的两个将在V'中。因此，已经找到了一种方式来使原始3-SAT问题成立。
  • 因此，已经证明了该问题是NP完全问题。

python代码：

def independent_set(G, T):
    def dfs(vertex, visited, chosen):
        # base case: if we have chosen T vertices, return True
        if len(chosen) == T:
            return True
        # explore the neighbors of the current vertex
        for neighbor in G[vertex]:
            # if neighbor is already chosen, skip
            if neighbor in chosen:
                continue
            # if neighbor has already been visited, skip
            if neighbor in visited:
                continue
            # add the neighbor to the chosen set
            chosen.add(neighbor)
            # mark the neighbor as visited
            visited.add(neighbor)
            # recursively explore the neighbors of the neighbor
            if dfs(neighbor, visited, chosen):
                return True
            # if the recursive call returns False, remove the neighbor from the chosen set
            chosen.remove(neighbor)
        # if we have explored all neighbors of the current vertex and haven't found a solution, return False
        return False
    
    # iterate over all vertices in the graph
    for vertex in G:
        # start a depth-first search from the current vertex
        visited = set([vertex])
        chosen = set([vertex])
        if dfs(vertex, visited, chosen):
            # if we have found a solution, return True
            return True
    # if we have explored all vertices and haven't found a solution, return False
    return False

其中，G是输入图的邻接表表示形式，T是独立集的大小阈值。该算法的时间复杂度为O(2^T * |V|)，因此对于较大的T和|V|可能不太实用。

引入ChatGPT部分参考，加上自己的理解：


from itertools import combinations

def is_independent_set(graph, t):
    vertices = graph.keys()
    for n in range(t, len(vertices)+1):
        for subset in combinations(vertices, n):
            valid = True
            for edge in graph.keys():
                if edge[0] in subset and edge[1] in subset:
                    valid = False
                    break
            if valid:
                return True
    return False