Assignment 7 — Reductions

CSC 349: Design and Analysis of Algorithms 
Assignment 7 — Reductions

Credit: This is a lab by Christopher Siu.
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 N P-Complete
problems.
Deliverables:
GitHub Classroom: https://classroom.github.com/a/m2Xn4Y9f
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 N P-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_g.txt graph_h.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.
1 of 4
CSC 349: Design and Analysis of Algorithms
Fall 2019
Assignment 7 — Reductions
Due: Friday, November 22nd
Alternatively, both the Subgraph Isomorphism implementation and its associated graph data structure can
be imported like any other Python module:
1 import graph
2 import subgraph_isomorphism as si
3
4 graph_g = graph.Graph()
5 graph_h = graph.Graph()
6
7 subgraph = si.isomorphic_subgraph(graph_g, graph_h)
…if G contains a subgraph isomorphic to H, subgraph_isomorphism.isomorphic_subgraph returns such a
subgraph. If not, it returns None.
Part 2: Clique to Subgraph Isomorphism
A clique is a subgraph within which every vertex is connected to every other vertex. The Clique problem
asks whether, given a graph G and an integer k, G contains a clique on k vertices.
For example, recall the following graph from above:
v0
v1
v2
v3
v4
This graph contains cliques on k = 1, k = 2, and k = 3 vertices, but not any cliques on k = 4 vertices.
In your programming assignment of choice per Assignment 1, implement an algorithm that, given a graph G
and a natural number k, uses the given Subgraph Isomorphism implementation to determine whether or not
G contains a clique on k vertices.
The specific input and output format of this implementation is up to you, as your code is the only code
that will make use of it. The only requirement is that you must use the given Subgraph Isomorphism
implementation; that is, your pseudocode should look something like:
Clique(G ← (V, E), k)
Input: A graph G and a natural number k
Output: Whether or not G contains a clique on k vertices
.
.
.
SubgraphIsomorphism(. . .)
.
.
.
…thereby reducing Clique to Subgraph Isomorphism, demonstrating that Subgraph Isomorphism is at least
as hard as Clique is.
Part 3: 3-SAT to Clique
The boolean satisfiability problem, or “SAT”, asks whether, given a proposition, there exists an assignment
of truth values to propositional variables that satisfies the proposition. The variation known as “3-SAT”
restricts the given propositions to conjunctive normal form with exactly 3 literals per clause.
2 of 4
CSC 349: Design and Analysis of Algorithms
Fall 2019
Assignment 7 — Reductions
Due: Friday, November 22nd
3-SAT can be reduced to Clique by representing the proposition as a graph, where:
· A vertex pi represents a literal p in clause i.
· Two vertices mi and nj are connected by an edge if and only if i 6= j and mi 6≡ ¬nj (m and n may or
may not be the same literal).
In other words, the edges of this graph indicate potential non-conflicting assignments of truth values between
different clauses. For example, given:
(p ∨ q ∨ r) ∧ (¬p ∨ r ∨ ¬p) ∧ (¬r ∨ ¬r ∨ ¬r)
…this proposition is represented by:
¬p2 r2 ¬p2
q1
p1
r1
¬r3
¬r3
¬r3
Since edges represent non-conflicting, inter-clause assignments, and we must make a set of assignments such
that at least one literal in every clause is true, and none of our assignments can conflict with each other, we
need to find a clique on k vertices within this graph, where k is the number of clauses in the given proposition.
The vertices of that clique then indicate the satisfying assignments; if no such clique can be found, then
no satisfying assignment exists. In the example above, finding a clique on k = 3 vertices yields that p ≡ F,
q ≡ T, and r ≡ F will satisfy the given proposition, a fact that is verified by the corresponding truth table:
p q r (p ∨ q ∨ r) (¬p ∨ r ∨ ¬p) (¬r ∨ ¬r ∨ ¬r) conjunction
T T T T T F F
T T F T F T F
T F T T T F F
T F F T F T F
F T T T T F F
F T F T T T T
F F T T T F F
F F F F T T F
In your programming language of choice per Assignment 1, implement an algorithm that, given a proposition
in CNF with exactly 3 literals per clause, uses your Clique implementation to determine whether or not the
proposition is satisfiable.
You must make use of your Clique implementation to solve 3-SAT, and, by extension, you must make use of
the given Subgraph Isomorphism implementation. By doing so, you have demonstrated that:
· Subgraph Isomorphism is at least as hard as Clique.
· Clique is at least as hard as 3-SAT.
Additionally, we have that:
· 3-SAT is known to be N P-Complete, and both Clique and Subgraph Isomorphism are in N P.
3 of 4
CSC 349: Design and Analysis of Algorithms
Fall 2019
Assignment 7 — Reductions
Due: Friday, November 22nd
…therefore, both Subgraph Isomorphism and Clique are also N P-Complete.
You may assume that the proposition will be well-formed, using ‘~’ to indicate negation, ‘&’ to indicate
conjunction, and ‘|’ to indicate disjunction3
. You may also assume that all propositional variables will be
one of the 26 lowercase English letters, and that a single space will appear between all literals and operators.
For example, the above proposition would be represented as:
( p | q | r ) & ( ~p | r | ~p ) & ( ~r | ~r | ~r )
Your program must accept as a command line argument the name of a file containing a proposition as
described above, then print to stdout its satisfiability according to the following format:
· If the proposition is satisfiable, the satisfying assignments must appear on a single line, sorted in
alphabetical order by their propositional variables.
· If the proposition is unsatisfiable, a message must indicate as such.
For example:
>$ ./compile.sh
>$ ./run.sh in1.txt
Satisfying assignment:
~p, q, ~r
You may further assume that the satisfying assignment, if one exists, will be unique4
. Your program will be
tested using diff, so its printed output must match exactly.
Part 4: Submission
The following items must be demonstrated in lab on the day of the deadline:
· A working program to solve Clique using the given program that solves Subgraph Isomorphism, as
specified — be prepared to show your source code.
The following files are required and must be pushed to your GitHub Classroom repository by the deadline:
· compile.sh — A Bash script to compile your submission (even if it does nothing), as specified.
· run.sh — A Bash script to run your submission, as specified.
The following files are optional:
· *.py, *.java, *.clj, *.kt, *.js, *.sh — The Python, Java, Clojure, Kotlin, Node.js, or Bash
source code files of a working program to solve 3-SAT using the given program that solves Subgraph
Isomorphism, as specified.
Any files other than these will be ignored.
Additionally:
· There will be two test runs, one after 8pm the date before the due date and one at the end of lab
(10am) on the due date. A feedback containing only what your program scores (on the same test cases
that will be used to grade it). I may be able to give you an idea of what your program is failing on (if
you have made an effort to test it), so please take advantage of these runs.
· Late submissions made within 24 hours of the deadline receive a .7 multiplier. If you decide to make a
late submission, please notify me by sending an email to vnguy143@calpoly.eduwith both the subject
and the body in the format: ”CSC349,late,asgn<i>”, i being the assignment number.
3That is, the standard bitwise operators.
4There are, in fact, 6 cliques on k = 3 vertices in the example above. However, this is due to the duplicate literals in the
latter clauses, and all of the cliques yield the same satisfying assignment.
4 of 4