二次时间顶点覆盖验证

Question

Suppose you are given an undirected graph G with n vertices and m edges represented by an n x n adjacency matrix A, and you are also given a subset of vertices S (represented by an array of size m). How can you check whether S is a vertex cover of G with quadratic time and space complexity?

根据顶点覆盖的定义，我知道我们要求每条边都必须与包含在 S 中的顶点相关联。

我可以很容易地想出一个三次算法：遍历邻接矩阵；每个 1 代表一条边 (u, v)。检查 u 或 v 是否在 S 中。如果没有，答案是否定的。如果我们到达邻接矩阵的末尾，答案是肯定的。

但是我怎样才能在 O(n^2) 时间内做到这一点？我想到目前为止我所做的唯一真正的 "observation" 是，如果我们已经在 S 中找到对应于该行的顶点，我们可以在迭代邻接矩阵时跳过中间行。但是，这对我帮助不大。

有人可以帮助我（或指出正确的方向）吗？

谢谢

Answer 1

构造一个数组T，它是所有不在S中的元素的位置。

然后：

for i in T:
    for j in T:
        if A[i][j] == 1:
            return False
return True

二次时间顶点覆盖验证

Quadratic-time vertex cover verification

algorithm

graph-theory