We can show that a problem B is at least as hard as a problem A by showing that an algorithm that solves B can be used to solve A

computer science


Assignment 7 — Reductions 

Due: Thursday, November 21st or Friday, November 22nd 

We can show that a problem B is at least as hard as a problem A by showing that an algorithm that solves B can be used to solve A. In this assignment, you’ll develop programs that use each other to solve NP-Complete problems. 


GitHub Classroom: https://classroom.github.com/a/Apwsw34_ Required Files: compile.sh, run.sh Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh 

Part 1: Subgraph Isomorphism Recall that two graphs, G = (VG, EG) and H = (VH, EH), are isomorphic if there exists a bijection f : VG → VH such that two vertices u, v ∈ VG are adjacent if and only if the corresponding vertices f (u), f (v) ∈ VH are also adjacent. In other words, two graphs are isomorphic if they have the same shape1 , even if their vertices are named differently. The Subgraph Isomorphism problem asks whether, given two graphs G and H, G contains a subgraph isomorphic to H. For example, given: G: H: v0 v1 v2 v3 v4 u3 u0 u1 u2 Here, G contains a subgraph isomorphic to H. Note that the reverse is not necessarily true: H does not contain a subgraph isomorphic to G. Further note that every graph contains a subgraph isomorphic to itself. The Subgraph Isomorphism problem is known to be NP-Complete; it is among the hardest problems to solve for which a solution can still be verified efficiently. The given subgraph_isomorphism.py implements a naïve, brute force algorithm2 to solve this problem. This implementation can be invoked from the command line, given two files containing edge lists: >$ python3 subgraph_isomorphism.py graph_g.txt graph_h.txt Isomorphic vertices: 0, 1, 2, 3 >$ echo $? 0 …if G contains a subgraph isomorphic to H, subgraph_isomorphism.py prints the vertices of that subgraph and terminates with exit status 0. If not, it terminates with exit status 1: >$ python3 subgraph_isomorphism.py graph_h.txt graph_g.txt No isomorphic vertices. >$ echo $? 1 1“isomorphic”, from Greek, “ίσόµορφος”, meaning “of equal form” 2 It’s not the most efficient known approach, but it is straightforward to read.

Related Questions in computer science category

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.