ECE 606, Fall 2022, Assignment 10

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ECE 606, Fall 2022, Assignment 10

Due: Tuesday, December 6, 11:59pm ET

Absolutely nO extensions!

(Same submission instructions as Assignment 1. No [python3] problems in this assignment.)

Note: when we say “algorithm” without qualification, we mean a deterministic algorithm.  Other kinds of algorithms are qualified, e.g., “non-deterministic algorithm” or “randomized algorithm” .

1.  Consider the following problem:  given as input (G, k) where G is an undirected graph that has a vertex cover of size k, output a vertex cover (i.e., subset of the vertices that is a vertex cover) of size k .

Prove that if there exists a polynomial-time algorithm for this problem, then P = NP.

Hint : by contradiction. Assume that there exists a polynomial-time algorithm for the prob- lem. Now devise a polynomial-time algorithm for the decision version of vertex cover, i.e., for the problem:  given an undirected graph G and an integer k, does G have a vertex cover of size k?

Philosophy:  consider the contrapositive of the statement.  It says that under the customary assumption P  NP, even if we know that a Sudoku puzzle has a solution, the solution is not necessarily easy to determine.

2. Look up what it means for two graphs to be isomorphic  to one another in your Textbook Part 2.  Suppose Iso is the decision problem that given two undirected graphs (G1, G2 ), are they isomorphic to one another?

Also recall from your Assignment 2:  given an undirected graph G, we say that it is non- trivially  automorphic  if it is ismorphic to itself via a mapping other than the identity.  Let

Auto be the decision problem: given an undirected graph G, is it non-trivially automorphic? Prove that Auto <c Iso.

3. Adopt the following problem definitions.

VertexCover: given as input (G, k) where G is an undirected graph, does G have a vertex cover of size k?

VertexCoverConn:  given as input  (G, k), where G is a connected undirected graph, does G have a vertex cover of size k?

VertexCoverNotConn: given as input (G, k), where G is an undirected graph that is not connected, does G have a vertex cover of size k?

Prove each of the following by construction.  “By construction” means that you should propose a function from instances of the problem to the left of the “<k” to instances of the problem to the right, that meets the “if and only if” property for <k, and is computable in polynomial- time.

· VertexCoverNotConn <k VertexCover

· VertexCover <k VertexCoverConn

· VertexCoverConn <k VertexCoverNotConn

4.  This problem addresses the reduction from CNF-SAT to CLIQUE in the proof of Claim 63 in your Textbook Part 11.  Suppose we have an instance of CLIQUE (G, 2), where G is the following undirected graph.

 

What are two different instances of CNF-SAT for which the reduction outputs this (same) instance of CLIQUE?

To clarify what “two different instances of CNF-SAT” means, we recall from Assignment 9 that an instance of CNF-SAT in n boolean variables encodes a function with domain {0, 1}n and codomain {0, 1}. What we seek are two instances of CNF-SAT (i.e., propositional logic formulae in CNF) which encode two different functions, but map to the above instance of CLIQUE under the reduction in the proof of Claim 63.

Philosophy: our intent is to show that the reduction is not an injection and therefore not a bijection. And we want to disallow superficial details such as the naming of boolean variables in the CNF-SAT instance and vertices in the graph that is part of the CLIQUE instance from getting in the way. E.g., the two CNF-SAT instances x1 v x2  and x3 v x4  are the same from the above standpoint because they encode the same function f : {0, 1}n → {0, 1}. As another example, the two instances (x1 v x2 ) V (x3 ) and (x3 ) V (x1 v x2 ) are the same.


2022-12-07