Description

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. 

Deliverables: 

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.