hmwk4.dvi
COMS 4236 Homework 4
Mengqi Zong < mz2326@columbia.edu >
March 25, 2018
Problem 1
First, the Partition Problem is in NP.
For a given partition, We can easily verify that, whether the two sums are equal or not
in polynomial time.
Second, Partition Problem is NP-hard.
We can reduce Subset Sum to Partition Problem. Let the sum of all integers in S be
s. If t ≥ s, then we already solved this problem. If t < s, then
• If t = s/2, then the Subset Sum is a Partition Problem.
• If t < s/2, then we can create a new set P = S∪{s−2t}. Then we try to see if P
can be equally partitioned. Since the sum of all integers in P is 2s− 2t, if P can
be equally partitioned, then the sum of each subcollection is s− t. Since number
s − 2t is in one of the subcollections, then the set S must have a subcollection
whose sum is t.
• If t > s/2, then we create a new set P = S ∪{2t− s}. And we try to see if P can
be equally partitioned. Since the sum of the integers in P is 2t− 2s, if P can be
equally partitioned, then the sum of each subcollection is t. Since number s− 2t
can only be in one of the subcollections, then the set S must have a subcollection
whose sum is t.
Note that this reduction takes polynomial time.
1
To sum up, Partition Problem is NP-complete.
Problem 2
a. First, the kernel can’t contain none of u, v.
If the kernel K does not include any nodes in u and v, then condition (2) of a kernel
can’t hold. Because u, v /∈ K and there are no other edges entering the nodes u, v. For
nodes u, v, they are neither in K nor have an incoming edge from some node in K.
Second, the kernel can’t contain both u and v.
If the kernel K contains both u and v, then condition (1) of a kernel can’t hold: for
nodes u, v ∈ K and there are edges (u, v), (v, u).
Third, the kernel can contain exactly one of the two nodes without violating the defi-
nition of a kernel.
To sum up, any kernel of G must include exactly one of the two nodes u, v.
b. Suppose there exists a kernel K of G such that any node in K does not contain
some node (distinct from u, v, w) that has an edge to at least one of the three nodes
u, v, w.
If there is no such edge that comes from some node in K that is distinct from the three
nodes, then some of the nodes of u, v, w must be in the kernel. Because, if none of the
three nodes is in the kernel, condition (2) can’t hold.
Suppose if some node in u, v, w is in the kernel. Without loss of generality, let u be in
the kernel. Then v can’t be in the kernel. Since w has only one coming edge (v, w)
and v is not in the kernel, then w must be in this kernel. However, since u, w are in K
and there is an edge (w, u), condition (1) can’t hold.
So, the assumption is not correct. And any kernel of G must contain some node x
(distinct from u, v, w) that has an edge to at least one of the three nodes u, v, w.
c. First, this problem is in NP.
2
For G = (V,E), we can easily verify if a subset K of V is the kernel of G in polynomial
time.
Second, We can reduce 3SAT to this problem.
For a given 3SAT problem, without loss of generality, suppose there are n variables
x1, x2, …, xn and m disjunction terms t1, t2, …, tm.
• First, we create 2n nodes to represent all the literals: nx1 , nx̄1 , …, nxn , nx̄n . And
for all i = 1, 2, …, n, we add edges (nxi , nx̄i) and (nx̄i , nxi) to the graph.
• Second, for each disjunction term, we create three new nodes u, v, w to form a
cycle u → v → w → u. The three nodes represent the three literals forming this
term. And then we create three edges from the respective literals to the nodes
in this new circle. For example, u, v, w represent literal x1, x̄2, x3, then we add
edges (nx1 , u), (nx̄2 , v), (nx3 , w) to the graph.
Note this reduction takes polynomial time.
We can prove that the kernel of the new graph contains exactly n nodes from nx1 , nx̄1 , …, nxn , nx̄n ,
and the n literals is the solution of the given 3SAT problem (The kernel may also con-
tain other nodes except from this n nodes).
• For every pair of nodes nxi and nx̄i , we have edges (nxi , nx̄i), (nx̄i , nxi) and there
are no other edges entering the nodes nxi and nx̄i . From part a, we know that
the kernel of the new graph must contain exactly one of the two nodes.
• As to the circles representing the disjunction terms, from the part b, we know
that the kernel must contain some node x (distinct from the nodes forming that
circle) that has an edge to at least one of the three nodes. As we can see, the
“some” node x to this disjunction term is the value to satisfy this term.
To sum up, this problem is NP-complete.
Problem 3
a. Suppose the optimal graph has cycles. Assume there’s a circle u → v → … → w → u
in the optimal graph, then we can remove one edge in the circle and still get all nodes
3
connected. Since all distances are positive integers, the modified graph has less total
distance than the previous optimal graph. In this case, the optimal graph with cycles
is not optimal, which contradicts with the assumption. So, the optimal graph is a tree
(every node has to be connected).
b. Given a number a, set N = {1, …, n} of n cities, a subset M ⊆ N of mandatory
cities, and the pairwise distances d(i, j) > 0, 1 ≤ i, j ≤ n between the cities, which are
assumed to be positive integers and symmetric. The problem is to find out if there
is a connected graph H=(V,E) that includes all mandatory cities and which has total
distance d(H) = Σ{d(i, j)|(i, j) ∈ E} that is at most a?
c. Basically, we will use binary search to do solve this optimization problem.
Given input with size n, we can conclude that the maximum total distance will have
no more than n bits, that is, no more than 2n. Because the input contains all distances
and bits represent edges, nodes. And the sum of the distances can’t be a number that
costs more than n bits.
Then what we do is to first calculate the total distance d, then use the subroutine to
check if d
2
satisfies. If d
2
returns 1, then check fracd
2
+ d2; if d
2
returns 0, then check
d
2
+0
2
.
And so on, until we find the optimal solution. This procedure takes O(log (2n)) = O(n)
times, and every time we call the subroutine which takes polynomial time. So in total,
this algorithm takes polynomial time.
d. First, the decision version of the Steiner tree problem is in NP.
We can easily verify if a the spanning tree is at most a in polynomial time.
Second, this problem is NP-hard. And we can reduce Node Cover to this problem.
Given Node Cover probelm with a graph G = (V,E), and number c. For every edge in
E, we create a new node to represent this edge in G’, and all the nodes form a set M.
For every node in V, we create a new node to represent this node in G’, and all the
nodes form a set N. As a result, for the new graph G’ = (V’, E’), V ′ = M ∪N .
As to the edges of G’,
• For u, v ∈ M,d(u, v) = d(v, u) = ∞.
4
• For u, v ∈ N, d(u, v) = d(v, u) = ∞.
• For u ∈ M, v ∈ N , if the edge represented by u connects the node represented
by v in graph G, d(u, v) = d(v, u) = 1. If not, d(u, v) = d(v, u) = ∞.
Note that this reduction takes polynomial time.
In this case, graph G has a vertex cover that of size at most c if and only if G’ has a
Steiner tree with total distance d(H) = |M |+ c− 1.
To sum up, the decision version of the Steiner tree problem is NP-complete.
Problem 4
a. In order to satisfy a DNF, we just need to satisfy at least one conjunction term. We
can choose the first conjunction term of the DNF, if xi is in this term, set xi to be 1;
if x̄i is in this term, set xi to be 0. As to the rest, we can arbitrarily set the value, for
example, all set to 0. Since the first conjunction term is satisfied, this DNF is satisfied.
In order to get the result, we at most need to scan entire the input (when there is only
one conjunction term in the DNF). So, the Satisfiability problem for Boolean formulas
in DNF is in P.
b. The complementary problem of DNF-TAUT is CP = {DNF formula F | ∃ assignment x, F (x) =
0}. We will prove that DNF-TAUT is coNP-complete by proving CP is NP-complete.
First, CP is in NP, because we can verify its result in polynomial time.
Second, We can reduce SAT to CP. For any given SAT problem, finding a satisfiable
assignment is equivalent to finding an unsatisfiable assignment of its negation. And we
can transform the negation of a CNF into a DNF in polynomial time. All we need to
do is to change all ∧ into ∨, change ∨ into ∧ and replace literal x with its counterpart x̄.
To sum up, CP is NP-complete. Since DNF-TAUT is the complementary problem of
CP, then DNF-TAUT is coNP-complete.
5
Problem 5
a. Optimality Testing problem for Π1 is in NP.
To solve this problem, all we need to do is to guess the a yopt that is the optimal
solution and check if this yopt is the same as y. Since |y| ≤ p(|x|), we can this problem
is in NP.
Optimality Testing problem for Π1 is in coNP.
For Π1, the complementary problem is y not an optimal solution for x. For that prob-
lem, we just guess the optimal solution yopt, and check if yopt and y are the same. Since
|y| ≤ p(|x|), the complementary problem is in NP. And Optimality Testing problem
for Π1 is in coNP.
To sum up, Optimality Testing problem for Π1 is in NP ∩ coNP .
As to Π2, since Π1 and Π2 are dual problems, they share the same optimal solution.
So, Optimality Testing problem for Π2 is also in NP ∩ coNP .
b. For Π1, the decision version is: “For a given x, k, if there exists a y that is a solution
of instance x of Π1, f1(x, y) <= k.”
First, we will prove Π1 is in NP.
We can guess the a solution yopt that has the minimum value of f1(x, y) for all y that
is the solution of instance x of Π1. Then check if f1(x, yopt) <= k, if it is, return 1.
Else return 0. As we can see, this problem is in NP.
Second, we will prove Π1 is in coNP. We will prove this by showing its complementary
problem is in NP.
The complementary problem is:” For a given x, k, if all y which is a solution of instance
x of Π1 that f1(x, y) > k.”
To solve this problem, We can guess the solution yopt that has the minimum value of
f1(x, y) for all y that is the solution of instance x of Π1. Then check if f1(x, yopt) > k,
if it is, then return 1. Else return 0. As we can see, this complementary problem is in
NP. So this problem is in coNP.
6
To sum up, Π1 is in NP ∩ coNP .
For Π2, the decision version is: “For a given x, k, if there exists a y that is a solution
of instance x of Π1, f1(x, y) >= k.”
First, we will prove Π2 is in NP.
We can guess the a solution yopt that has the minimum value of f2(x, y) for all y that
is the solution of instance x of Π2. Then check if f2(x, yopt) >= k, if it is, return 1.
Else return 0. As we can see, this problem is in NP.
Second, we will prove Π2 is in coNP. We will prove this by showing its complementary
problem is in NP.
The complementary problem is:” For a given x, k, if all y which is a solution of instance
x of Π2 that f1(x, y) < k.”
To solve this problem, We can guess the solution yopt that has the maximum value of
f2(x, y) for all y that is the solution of instance x of Π2. Then check if f2(x, yopt) > k,
if it is, then return 1. Else return 0. As we can see, this complementary problem is in
NP. So this problem is in coNP.
To sum up, Π2 is in NP ∩ coNP .
So the decision version of both optimization problems is in NP ∩ coNP .
7