Formally, a vertex-cover of an undirected graph is a subset V′ of V such that if edge (u, v) is an edge of G, then u is in V′, or v is in V′, or both. The set V′ is said to "cover" the edges of G. The following figure shows examples of vertex covers in two graphs (and the set V' is marked with red).
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.
- Assume that every vertex has an associated cost of .
minimize (minimize the total cost) subject to for all (cover every edge of the graph) for all . (every vertex is either in the vertex cover or not)
- Python implementation(running-time: exponential)
import itertools class Vertex_Cover: def __init__(self, graph): self.graph = graph def validity_check(self, cover): is_valid = True for i in range(len(self.graph)): for j in range(i+1, len(self.graph[i])): if self.graph[i][j] == 1 and cover[i] != '1' and cover[j] != '1': return False return is_valid def vertex_cover_naive(self): n = len(self.graph) minimum_vertex_cover = n a = list(itertools.product(*["01"] * n)) for i in a: if Vertex_Cover.validity_check(ins, i): counter = 0 for value in i: if value == '1': counter += 1 minimum_vertex_cover = min(counter, minimum_vertex_cover) return minimum_vertex_cover if __name__ == '__main__': graph =[[0, 1, 1, 1, 1],[1, 0, 0, 0, 1],[1, 0, 0, 1, 1], [1, 0, 1, 0, 1], [1, 1, 1, 1, 0]] ins = Vertex_Cover(graph) print 'the minimum vertex-cover is:', Vertex_Cover.vertex_cover_naive(ins)