CSC349-Assignment 7 Reductions Solved

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.

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 shape[1], 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:

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_g.txt graph_h.txt No isomorphic vertices.

$ echo $?

1

 

1

Alternatively, both the Subgraph Isomorphism implementation and its associated graph data structure can be imported like any other Python module:

 1import graph

2import subgraph_isomorphism as si

3

4graph_g = graph.Graph()

5graph_h = graph.Graph()

6

7subgraph = 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:

 

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

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:

 

p
q
r
(p ∨ q ∨ r)
(¬p ∨ r ∨¬p)
(¬r ∨¬r ∨¬r)
 
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
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: conjunction

In your programming language of choice per Assignment 1, implement an algorithm that, given a proposition in CNF with exactly [2] 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 NP-Complete, and both Clique and Subgraph Isomorphism are in NP.

…therefore, both Subgraph Isomorphism and Clique are also NP-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 unique[3]. Your program will be tested using diff, so its printed output must match exactly.


 
[1] of 4
[2] of 4
[3] of 4