图中最小团数的算法复杂度

Question

我已经编写了一个算法来解决图中的最小团数问题。我已经测试了我的回溯算法，但我无法计算出最坏情况的时间复杂度，我已经尝试了很多次。

我知道这个问题是一个NP难问题，但是我觉得有没有可能根据代码给出一个最坏的时间复杂度。这段代码的最差时间复杂度是多少？任何想法？如何形式化递归方程？

我尝试编写易于理解的代码。如果您有任何问题，请发表评论。我将非常高兴获得提示、引用和答案。感谢小伙伴们的提示:)。

编辑正如 M C 评论的那样，我基本上已经尝试解决这个问题 Clique cover problem

伪代码:

function countCliques(graph, vertice, cliques, numberOfClique, minimumSolution)
    for i = 1 .. number of cliques + 1 new loop
        if i > minimumSolution then 
            return;
        end if
        if (fitToClique(cliques(i), vertice, graph) then
            addVerticeToClique(cliques(i), vertice);
            if (vertice == 0) then //last vertice 
                minimumSolution = numberOfClique
                printResult(result);
            else 
                if (i == number of cliques + 1) then // if we are using a new clique the +1 always a new clique
                    countCliques(graph, vertice - 1, cliques, number of cliques + 1, minimum)
                else 
                    countCliques(graph, vertice - 1, cliques, number of cliques, minimum)
                end if
            end if 
            deleteVerticeFromClique(cliques(i), vertice);
        end if
    end loop
end function


bool fitToClique(clique, vertice, graph) 
    for ( i = 1 .. cliqueSize) loop 
        verticeFromClique = clique(i)
        if (not connected(verticeFromClique, vertice)) then 
            return false
        end if
    end loop
    return true
end function

代码

int countCliques(int** graph, int currentVertice, int** result, int numberOfSubset, int& minimum) {
// if solution
if (currentVertice == -1) {
    // if a better solution
    if (minimum > numberOfSubset) {
        minimum = numberOfSubset;
        printf("New minimum result:\n");
        print(result, numberOfSubset);
    }
    c++;
} else {
    // if not a solution, try to insert to a clique, if not fit then create a new clique (+1 in the loop)
    for (int i = 0; i < numberOfSubset + 1; i++) {
        if (i > minimum) {
            break;
        }
        //if fit
        if (fitToSubset(result[i], currentVertice, graph)) {
            // insert
            result[i][0]++;
            result[i][result[i][0]] = currentVertice;
            // try to insert the next vertice
            countCliques(graph, currentVertice - 1, result, (i == numberOfSubset) ? (i + 1) : numberOfSubset, minimum);
            // delete vertice from the clique
            result[i][0]--;
        }
    }
}
return c;
}


bool fitToSubset(int *subSet, int currentVertice, int **graph) {
    int subsetLength = subSet[0];
    for (int i = 1; i < subsetLength + 1; i++) {
        if (graph[subSet[i]][currentVertice] != 1) {
            return false;
        }
    }
    return true;


  }

void print(int **result, int n) {
    for (int i = 0; i < n; i++) {
        int m = result[i][0];
        printf("[");
        for (int j = 1; j < m; j++) {
            printf("%d, ",result[i][j] + 1);
        }
        printf("%d]\n", result[i][m] + 1);
    }
}

int** readFile(const char* file, int& v, int& e) {
int from, to;
int **graph;
FILE *graphFile;
fopen_s(&graphFile, file, "r");

fscanf_s(graphFile,"%d %d", &v, &e);

graph = (int**)malloc(v * sizeof(int));

for (int i = 0; i < v; i ++) {
    graph[i] = (int*)calloc(v, sizeof(int));
}

while(fscanf_s(graphFile,"%d %d", &from, &to) == 2) {
    graph[from - 1][to - 1] = 1;
    graph[to - 1][from - 1] = 1;
}
fclose(graphFile);
return graph;
}

Answer 1

您算法的时间复杂度与列表密切相关 compositions一个整数，其中有 O(2^N)。

虽然有规则，但仅靠组合是不够的，因为还有组合方面。具体来说，一个团必须包含编号最高的未使用顶点。

一个例子是组合 2-2-1 (N = 5)。第一个团必须包含 4，将未使用的顶点数减少到 4。然后可以在 4 个元素中的 1 个元素之间进行选择，未使用的顶点现在为 3。已知第二个团的 1 个元素，因此有 2 个未使用的顶点。因此，必须在 2 个元素中的 1 个之间进行选择，以决定第二个团中的最终顶点。这只为最后一个集团留下一个顶点。对于这个组合，有 8 种可能的制作方式，由 (1*C(4,1)*1*C(2,1)*1) 给出。 8种可能的方式如下:

(5,4),(3,2),(1)
(5,4),(3,1),(2)
(5,3),(4,2),(1)
(5,3),(4,1),(2)
(5,2),(4,3),(1)
(5,2),(4,1),(3)
(5,1),(4,3),(2)
(5,1),(4,2),(3)

上面的示例显示了最坏情况所需的格式，即组合中包含尽可能多的 2。我认为这仍然是 O(N!)，尽管它实际上是 (N-1)(N-3)(N-5)...(1 ) 或 (N-1)(N-3)(N-5)...(2)。然而，这是不可能的，因为如图所示，它需要一个完整的图，它会立即被捕获，并将图限制为一个集团，其中只有一个解决方案。

考虑到构图的变化，可能的构图数量可能是 O(2^N) 上限的合理起点。有 O(3^(N/3)) 个最大派系是另一个有用的信息，因为该算法理论上可以找到所有派系。尽管这还不够好，因为一些最大派系被发现多次，而另一些则根本没有。

由于两个主要原因，很难设置更严格的上限。首先，该算法逐渐限制派系的最大数量，我想你可以称之为组合的大小，这对每个派系花费的计算时间设置了上限。其次，缺失的边缘会导致大量可能的变化被忽略，这几乎可以确保忽略绝大多数 O(N!) 变化。结合上面的段落，使得上界变得困难。如果这还不够答案，您可能想将问题带到堆栈交换的数学领域，因为更好的答案将需要相当多的数学分析。