### Vertex Cover (python implementation)

MINIMUM VERTEX-COVER
Description
Formally, a vertex-cover of an undirected graph $G=(V, E)$ 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 $\tau$ 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 $c(v)\geq 0$.
 minimize $\sum_{v \in V} c(v) x_v$ (minimize the total cost) subject to $x_u+x_v\geq 1$ for all $\{u,v\} \in E$ (cover every edge of the graph) $x_v\in\{0,1\}$ for all $v\in V$. (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)