Problem Set 8: Final Project¶
CSC427, semester 202 (jan-may 2020)
burton rosenberg
univ of miami
(c) 2020 all rights reserved
Created: 20 April 2020
Last update: 21 April 2020
Student’s Name: (your name here)¶
Statement of the project¶
In this final project, the study of P and NP will be practiced.
Your tasks are to,
1- Write a polynomial time predicate VerifyPath.find_if_path, that given a graph and two vertices, returns true if the two vertices are vertices in the graph, and there is a path in the graph connecting the two vertices. Else it returns False.
2- Write a polynomial time predicate VerifyKCover.verify, that given a graph and a list of vertices, returns true if the list of vertices is a vertex-covering of the graph. That is, ever edge of the graph has at least one end vertice in the given cover. Else it returns False.
3- Write an exponential time search algoirthm, SolveKCover.search_brute_force, that given a graph and an integer k, returns a vertex-covering with exactly k vertices of the graph, or else returns the empty list. The algorithm will work by enumerating all subsets of k vertices from the set of all the graph’s vertices, and will apply the verifying on each such candidate solution.
4- Write a polynomial time reduction Reduction.reduce from 3-SAT to Vertex Cover, that is, which given an instance of 3-SAT produces a graph and a number k, such that 3-SAT is satisfiable if and only if the graph has a k covering.
5- Write a polynomail time function Reduction.pullback, which given a 3-SAT to Vertex Cover reduction, and a k cover, produces a satisfying assignment for the 3-SAT instance, the subject of the reduction.
6- Put it all together: Write a 3-SAT solver that solves a 3-SAT instance by reducing it to a Vertex Cover instance, solves the instance by brute force, and pulls back the vertex cover solution to a satisfying assignment for the 3-SAT instance.
Description of data structure¶
Description of a graph
1- A graph is made up of vertices and edges. Each edge is a pair of vertices
2- A vertex will be represented as a string, to be thought of as the name of the vertex.
3- An edge will be represented as a Python pair. The two members of the pair will be the vertex name.
4- A graph will be a Python list of pairs.
In [1]:
# Example of a graph. The textbook graph of Figure 0.12 (b) is represented –
figure_0_12_b = [
(‘1′,’2’),
(‘1′,’3’),
(‘1′,’4’),
(‘2′,’3’),
(‘2′,’4’),
(‘3′,’4’)
]
Description of a 3-SAT
1- A 3-SAT is made up of clauses, signed variables, and variables.
2- A variable will be represented as a string, to be thought of as the name of the variable.
3- A signed variable is a Python pair. The first element is a variable name and the second element is 0 or 1.
• If 0, the sign of the variable is positive, the variable is appearing without negation;
• If 1, the sign of the variable is negative, the variable is appearing negated.
4- A clause is Python list of 3 signed variables.
5- An instance of 3-SAT is a Python list of clauses.
In [2]:
# The 3-SAT in Figure 7.33 is represented –
figure_7_45 = [
[(‘x1’,0),(‘x1’,0),(‘x2’,0)],
[(‘x1’,1),(‘x2’,1),(‘x2’,1)],
[(‘x1’,1),(‘x2’,0),(‘x2’,0)]
]
Description of an instance of k-VC
An instance of a k vertex cover problem is a Python pair.
• The first element of the pair is the integer k
• The second element of the pair is a graph
Student workspace¶
P-Time Path algorithm¶
In [3]:
class VerifyPath:
@staticmethod
def find_if_path(graph,source,dest):
pass
# data structures:
# visited, a set of visited vertices
# edge_dict, a dictionary from a vertex to a list of neighbors
# q, a list of unvisited vertices, known to be reachable
# from source, to be visited
visited = set([source])
edge_dict = {source:[]} # should be a list of neighbors of source
q = edge_dict[source]
pass
while len(q)>0:
pass
pass
return dest in visited
P-Time Vertex Cover verifier¶
In [4]:
class VerifyKCover:
def __init__(self,graph,verbose=set()):
self.graph = graph
self.verbose = verbose
def verify(self,cover):
“””
verify that the vertex list given is a k-cover
“””
pass
return True
Exp-Time Vertex Cover solver¶
In [5]:
class SolveKCover:
def __init__(self,graph,verbose=set()):
self.graph = graph
self.verbose = verbose
self.verifier = VerifyKCover(graph,verbose)
self.iterate_idx = 0
self.k = 0
# make a list of vertices of the graph
v = set()
for edge in graph:
v.add(edge[0])
v.add(edge[1])
self.vertices = list(v)
def get_vertices(self):
return self.vertices
def get_verifier(self):
return self.verifier
def get_ith_bit(self,i,n):
return (n//2**i)%2
def count_ones(self,n):
count = 0
while n>0:
count += n%2
n = n//2
return count
def new_iteration(self,k):
self.k = k
self.iterate_idx = 0
def next_iterate(self):
idx = self.iterate_idx + 1
while (self.count_ones(idx)!=self.k):
idx += 1
self.iterate_idx = idx
return idx
def select_vertices_by_index(self,idx):
l = len(self.vertices)
i = 0
selected = []
while idx>0 and i
return []
if k<=0:
return []
assert(k>0)
pass
return []
Some examples of how to use the enumerating functions¶
In [6]:
# using the functions implemented in SOlveKCover to
# enumerate the integers with binary representation
# containing exact one 1 bit. e.g. 1, 2, 4, …
def iterator_pure_powers(n_max):
skc = SolveKCover([(‘a’,’a’)])
skc.new_iteration(1)
idx = skc.next_iterate()
while idx
print(s.get_verifier().verify(solution))
False
False
True
True
In [9]:
figure_7_45 = [
[(‘x1’,0),(‘x1’,0),(‘x2’,0)],
[(‘x1’,1),(‘x2’,1),(‘x2’,1)],
[(‘x1’,1),(‘x2’,0),(‘x2’,0)]
]
Reduction.reduce(figure_7_45)
print(Reduction.solve(figure_7_45))
sat_1 = [
[(‘a’,0),(‘b’,0),(‘c’,0)]
]
print(Reduction.solve(sat_1))
sat_2= [
[(‘a’,1),(‘a’,1),(‘a’,1)]
]
print(Reduction.solve(sat_2))
sat_3 = [
[(‘a’,0),(‘b’,0),(‘c’,0)],
[(‘a’,1),(‘b’,1),(‘c’,1)]
]
print(Reduction.solve(sat_3))
[]
[]
[]
[]
In [ ]: