hw4
Problem Set 4
Problem 1
Prove Partition Problem in
A non-deterministic polynomial time machine can guess a partition of the number set and
accept if the two subcollections after partition have equal sum.
Prove Subset Sum is polynomial time reducible to
Partition Problem
Given of positive intefers and another positive integer , suppose the total sum of numbers
in collection is , Let = .
Obviously, is also collection of positive integers.
Now we prove that there is a subcollection of whose sum is equal to if and only if there is a
partition of the collection into two subcollections whose sum are equal.
T = 2t
In this case .
If there is a subcollection of whose sum is equal to , then the complement of this
subcollection has sum = = . Thus collection can be partitioned into two
subcollections whose sum are equal (both equalt to ).
If can be partitioned into two subcollections whose sum are equal, because total sum is ,
then the sum of both subcollections must be equalt to , thus there is a subcollection of
whose sum is equal to .
T – 2t < 0 The sum of is . If there is a subcollection of whose sum is equal to , it is also subcollection of , the complement of this subcollection in also have sum . Thus collection can be partitioned into two subcollections whose sum are equal (both equalt to ). If can be partitioned into two subcollections whose sum are equal, because total sum is , then the sum of both subcollections must be equalt to , The newly added element is in one of the subcollections, all elements in another subcollection comes from , thus there is a subcollection of whose sum is equal to . T - 2t > 0
The sum of is .
If there is a subcollection of whose sum is equal to , the complement of it in is
. Take as one subcollection in , the complement of in has sum
= . Thus collection can be partitioned into two subcollections whose
sum are equal (both equalt to ).
If can be partitioned into two subcollections whose sum are equal, because total sum is
, then the sum of both subcollections must be equalt to , The newly added
element is in one of the subcollections, all elements in another subcollection denoted as
comes from , has sum , the complement of in has sum ,
thus there is a subcollection of whose sum is equal to .
Summary
Note that, we only add 0 or 1 element to to construct . Thus, the reduction takes
polynomial time. Combined with the proof in 3 cases, we have proven that NP-Complete
problem Subset Sum is polynomial time reducible to Partition Problem .
Because `Partition Problem is in and there is one NP-Complete problem that is
polynomial time reducible to Partition Problem , Partition Problem is also NP-complete.
Problem 2
a
Every node is either itself in K or has an incoming edge from some node in K.
For node , apart from , there is no other node that has edge entering it. Only has edge
entering it. Thus, node is either itself in K or has an incoming edge from in K. In
another word, either in or in . Because there is edge , thus we can’t have both
and in .
For node , with the same reasoning, it also requires that either or in but not both.
Thus, any kernel of G must include exactly one of the two nodes .
b
For any kenel , suppose there is no node in (distinct from u,v,w) that has an edge to any
of the three nodes .
For node , apart from , there is no other possible node in that has edge entering it.
Because every node is either itself in K or has an incoming edge from some node in K. Thus
either or in . Because there is edge , thus we can’t have both and in .
For node , with the same reasoning, either or in , but not both.
For node , with the same reasoning, either or in , but not both.
Thus, we need to satisfy the following 3 conditions.
1. either or in , but not both.
2. either or in , but not both.
3. either or in , but not both.
If in , then from 1 not in , from 2 not in , which is a contradiction to 3.
If not in , then from 1, in , from 2 in , which is a contradiction to 3.
Thus, in either case, we have a contradiction. And the assumption doesn’t hold. So we have
proven that 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
Graph construction from 3SAT formula
For a fomula in CNF, we can construct the graph as follows.
1. For each variable in , add edge and to .
2. For each clause , add the following cycle to and for each literal
in , add the 3 edges , , to .
Prove: if is satisfiable, then has a kernel
if is satisfiable, for each variable , if the solution assigns true, then select the node in ,
if the solution assigns false, then select the node in .
Due to our selection rule, either node or is selected. The kernel requirment for the graph
part constructed in step 1 satisfied.
For each clause, at least 1 literal makes true, correspondingly, at least 1 selected literal node
has an edge to one of the 3 nodes in the clause cycle in . If there is only 1 clause node having
literal node entering it, we can select the next clause node of this clause node to . Thus, The
kernel requirment for the graph part 2 constructed in step 2 satisfied.
In summary, we can take the corresponding literal node to the 3SAT assignment plus additional
clause node if necessary to form a kernel for .
Prove: if has a kernel, then is satisfiable
If has a kernel , for each variable , from proof of part , we know that either or in .
If in , we assign true in , if in , we assign false in . For each clause , from proof
of part b, we know that contains some literal node that has an edge to at least one of the 3
nodes . According to our graph construction rule, the corresponding literal belongs to
the clause , in another word, at least 1 clause is true under the assignment corresponding to
the kernel. Thus, each clause is satisfied under the assignment. Thus is satisfiable.
Summary
Obviously, the graph construction takes polynomial time. And we have proven that the formula
is satisfiable if and only if the corresponding graph has a kernel. Thus, 3SAT is polynomial time
reducible to directed graph kernel problem. In addition, a non-deterministic polynomial time
machine can guess a subset of the nodes and then verify whether it is a kernel. The kernel
problem is in . Thus, it is NP-complete to determine whether a given directed graph has a
kernel.
Problem 3
1
The optimal graph is connected. If there is a cycle in the optimal graph, we can remove one
edge from the cycle and the resulting graph is still connected and have all the cities in the
optimal graph. Thus, the resulting graph still meets the requirement but with less total distance
(because all distances are positive). This is a contradiction to the fact that the optimal graph has
minimum total distance.
Thus, the optimal graph is connected and have no cycle, it is a tree.
2
Given an integer , a set N={1,…,n} of n cities, a subset M N of mandatory cities (the rest are
optional), and the pairwise distances d(i,j)>0, 1≤ i,j ≤n between the cities, , which are assumed to
be positive integers and symmetric.
Is there a tree that includes all the mandatory cities and has total distance at most
?
3
Suppose the total distance of all city pairs are . The optimal value can be obtained using
binary search with initial interval [0, D]. In each iteration, invoke the decision version subroutin
to determine to continue the search in which half of the interval. The search ends until the
interval contains only one integer which is the optimal value.
Suppose the input is encoded in bits, obviously . The binary search will have
iterations. In each iteration, it takes polynomial time to call the decision
version subroutin. The total time taken is still polynomial.
low = 01
4
decision version of the Steiner tree problem in NP
Because given a graph H=(V,E) , we can verify in polynomial time whether the graph is a tree,
including all the mandatory cities and the total distances is less than or equal to . Thus
decision version of the Steiner tree problem is NP.
Prove Node Cover is polynomial time reducible to decision version of the
Steiner tree problem where all the distances are 1 or
Given a graph in the node cover problem, we can construct the input for Steiner
tree as follows.
There are cities. Each node in is taken as a city and each edge in is also
taken as a city. The edge cities are mandatory.
Construct the distances matrix as follows.
Prove if there is a tree that includes all the mandatory cities have size
then there is a node cover of size
high = D
while low < high:
k = floor((high + low) / 2)
if there is a tree that includes all the mandatory cities and has
total distance at most k:
high = k
else:
low = k + 1
return (low)
initially set all d[i][j] = infinity
for u in V:
for v in V:
d[u][v] = 1
for e in E:
u, v are the two nodes of e
d[u][e] = d[e][u] = 1
d[v][e] = d[e][v] = 1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
9
10
Let a tree that includes all the mandatory cities is . Suppose the total distance is
.Because distance between the two cities is 1, thus Because any
edge city in is connected to only its two nodes and . Thus either or will be in . The
edges are all covered by the node cities in . Thus, the node cities in is a node cover of
which has size .
Prove if there is a node cover of size then there is a tree that includes
all the mandatory cities have size
Let be a node cover in . Because d[u][v]=1 for all pairs of node u and v. Thus, we can
first construct a tree spanning , then add the edges to the edge city to include all the
manatory edge cities. Because d[u][e]=1 for each node u and its edge. Thus, we can add
additional edges to form the tree that includes all mandatory cities. The tree will have
edges, thus the total distance is .
Summary
Thus there is a node cover in of size at most k if and only if there is a tree that includes all the
mandatory cities at most with the cities, mandatory cities and distances given
above. Obvious, it takes polynomial time to conduct the reduction. Thus Node Cover is
polynomial time reducible to decision version of the Steiner tree problem where all the
distances are 1 or .
From above, we have proven that the decision version of the Steiner tree problem is NP-
complete even if all the distances are 1 or .
Problem 4
(a)
A formula F in DNF is satisfiable if and only if there is at least one of its clauses are satisfiable.
The clause is satisfiable if and only if no such variable that itself and its negation appear in the
clause at the same time.
From this, we have the following algorithm to decide if a given formula in DNF is satisfiable. The
algorithm scans all the clauses in the worst case. Obviously, it takes polynomial time. Thus the
Satisfiability problem for Boolean formulas in DNF is in P.
Given formula F in DNF
for each clause in F:
if there is a variable and its negation both appear in the clause:
continue
else:
return true
return False
1
2
3
4
5
6
7
8
(b)
We can prove is coNP-complete by proving that its complement
{DNF formula F |there is an assignment that makes F false } is NP-
complete.
Because a non-deterministic polynomial time machine can guess an assignment and verify
whether the assignment makes the formula false, is in NP.
For a formuale in CNF, we can convert to DNF in polynomial time. is satisfiable if and
only if there is an assignment that makes false. Thus, is polynomial time reducible to
.
Thus, is NP-complete, is coNP-complete.
Problem 5
1
NP for
A non-deterministic polynomial time machine can guess the optimal value for and check
whether .
CoNP for
The complement problem is Is y not an optimal solution for x .
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, compute , verify that .
NP for
A non-deterministic polynomial time machine can guess the optimal value for and check
whether .
CoNP for
The complement problem is Is y not an optimal solution for x .
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, compute , verify that .
2
Decision problem:
Given instance in and value is there a solution for and
NP
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, compute , verify that .
CoNP
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, verify that it is optimal (NP proved in part 1), and verify that .
Decision problem:
Given instance in and value is there a solution for and
NP
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, compute , verify that
CoNP
A non-deterministic polynomial time machine can guess a candidate , verify that
holds, verify that it is optimal (NP proved in part 1), and verify that .
Problem Set 4
Problem 1
Prove Partition Problem in NP
Prove Subset Sum is polynomial time reducible to Partition Problem
T = 2t
T - 2t < 0
T - 2t > 0
Summary
Problem 2
a
b
c
Graph construction from 3SAT formula
Prove: if \phi is satisfiable, then G has a kernel
Prove: if G has a kernel, then \phi is satisfiable
Summary
Problem 3
1
2
3
4
decision version of the Steiner tree problem in NP
Prove Node Cover is polynomial time reducible to decision version of the Steiner tree problem where all the distances are 1 or \infty
Prove if there is a tree that includes all the mandatory cities have size k + |E| – 1 then there is a node cover of size k
Prove if there is a node cover of size k then there is a tree that includes all the mandatory cities have size k + |E| – 1
Summary
Problem 4
(a)
(b)
Problem 5
1
NP for \Pi_1
CoNP for \Pi_1
NP for \Pi_2
CoNP for \Pi_2
2
\Pi_1
NP
CoNP
\Pi_2
NP
CoNP