Naivete Implemented

from itertools import *

def validity_check(cover, graph):
	assert len(graph) == len(cover)
	n = len(graph)

	for i in range(0, n):
		for j in range(i+1, n):
			if graph[i][j]==1 and cover[i]!=1 and cover[j]!=1:
				return False
	return True

def vertex_cover_naive(input_graph):
	n = len(input_graph)
	minimum_vertex_cover = n
	for assignment in product([0, 1], repeat=n):
		if(validity_check(assignment, input_graph, n)):
			size = sum(assignment)
			if minimum_vertex_cover > size:
				minimum_vertex_cover = size
	return minimum_vertex_cover

def test():
	graph = [[0, 1, 1, 1, 1],
		[1, 0, 0, 0, 1],
		[1, 0, 0, 1, 1],
		[1, 0, 1, 0, 0],
		[1, 1, 1, 1, 0]]

	asseret vertex_cover_naive(graph) == 3

For each vertex v in G:
	if_better:
		assign "1" to v
	else:
		assign "0" to v
if assignment is valid:
	if size of assignment is at most k:
		return "Yest"
return "No"