Description

(1).Organize Problem
S (Total set of problem) = {1, 2, 3,…, i,…, n}
Where, 1 ≤ i ≤ n
Score set = {𝑠1, 𝑠1, … , 𝑠𝑖, … , 𝑠𝑛}
Score set can be partitioned into two sets A and A̅ (A̅ = S − A), for example
∑ 𝑠𝑖 = ∑ 𝑠𝑗
𝑖∈𝐴 𝑗∈𝐴̅
Goal: Show that SET-PARTITION is NP-Complete
The problem says I need separate the set of ice cream by two baskets named 𝐵1 𝑎𝑛𝑑 𝐵2, which must have same score sum. Thus, I think it is two-partition problem, and I use A and A̅ (𝑛𝑜𝑡 𝐴) instead of 𝐵1 𝑎𝑛𝑑 𝐵2. Now, I prove this problem is NP-Complete.
(2).Procedure
Step1. There is non-deterministic polynomial-time algorithm that solves A, i.e., A ∈ NP
Step2. Any NP-Complete Problem B can be reduced to A
Step3. The reduction of B to A works in Polynomial time
Step4. The original problem A has a solution if and only if B has a solution.
(3).Step1
SET-PARTITION ∈ NP: Guess the two partitions and verify that the two have equal sums
(a).Prove the algorithm can be solved in polynomial time
This problem can be solved by dynamic programming, if the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible.
I use the set which I mentioned above, S = {𝑥1, 𝑥2, 𝑥3,…, 𝑥𝑖,…, 𝑥𝑛}. And K is the sum of all elements’ score in S. that is K = 𝑠1 + ⋯ + 𝑠𝑛. I will build an algorithm that determines
𝐾 whether there is a subset of S that sums to ⌊ ⌋
2
𝐾
Recurrence relation: I determine if there is a subset of S that sums to ⌊ ⌋. Let p(I,j) be True if
2
𝐾 a subset of {𝑥1, 𝑥2, 𝑥3,…, 𝑥𝑗}. sums to i and False otherwise. Then p(⌊2⌋,N) is True if and
𝐾 only if there is a subset of S that sums to ⌊ ⌋. The goal of the algorithm will be to compute
2
𝐾
p(⌊ ⌋,N). Then I have recurrence relation:
2
𝑇𝑟𝑢𝑒, 𝑖𝑓 𝑒𝑖𝑡ℎ𝑒𝑟 𝑝(𝑖, 𝑗 − 1)𝑖𝑠 𝑇𝑟𝑢𝑒 𝑜𝑟 𝑝(𝑖 − 𝑥𝑗, 𝑗 − 1)
𝑝(𝑖, 𝑗) = {
𝐹𝑎𝑙𝑠𝑒, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Then, the algorithm’s running time is:
𝐾
O ( × 𝑛) = 𝑂(𝑘 × 𝑛)
2
Thus, the running time is polynomial and this algorithm is NP.
(b).SUBSET-SUM:
Given a sequence 𝑎1, … , 𝑎𝑛, 𝑡 of nonnegative integers, decide whether there is a subset A ∈ {1, … , n} such that
∑ 𝑎𝑖 = 𝑡
𝑖∈𝐴
(c).SET-PARTITION:
Given a sequence 𝑎1, … , 𝑎𝑛 of nonnegative integers, decide whether there is a subset A ∈
{1, … , n} such that
∑ 𝑎𝑖 = ∑ 𝑎𝑗
𝑖∈𝐴 𝑗∈𝐴̅
(4).Step2
Reduction of SUBSET-SUM to SET-PARTITION: SUBSET-SUM is defined as follow: Given a set X = {𝑎1, … , 𝑎𝑛} and a target number t of nonnegative integers, find a subset Y ∈ X such that:
𝑛
∑ 𝑎𝑖 = 𝑘 (𝑠𝑢𝑚 𝑜𝑓 𝑎𝑙𝑙 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑋)
𝑖=1
∑ 𝑎𝑖 = 𝑡 (𝑖𝑓 𝑖 𝑖𝑠 𝑏𝑒𝑙𝑜𝑛𝑔 𝑡𝑜 𝑌)
𝑖∈𝑌
That is, the members of Y add up to exactly t, let k be the sum of member of X.
Feed X′ = X ∪ {k − 2t} = 2k − 2t into SET-PARTITION. Accept if and only if SETPARTITION accepts.
(5).Step3
This reduction clearly works in polynomial time.
(6).Step4
I will prove that < X, t > ∈ SUBSET-SUM, iff < X′ >∈ SET-PARTITION
Where sum(X′) = 2k – 2t.
⚫ If there exists a set of numbers in X that sum to t, then the remaining numbers in X sum to k- t. Therefore, there exists a partition of X′ into two such that each partition sums to k- t.
⚫ Let’s say that there exists a partition of X′ into two sets such that the sum over each set is k – t. One of these sets contains the number k-2t. Removing this number, I get a set of numbers whose sum is t, and all of these numbers are in X
Problem2 (NP-complete)
(1).Organize Problem
Given an undirected graph G = (V, E), where nodes represent towns and edges represent roads, and given a number k, is there a way to build k bunkers in k different towns so that every town either has its own bunker, or is connected by a direct road to a town that does have a bunker?
(2).Shows PYGMALION is in NP
A candidate solution is a subset of the vertices, C ∈ V. I must check the number of vertices |𝐶| doesn’t exceed k, to verify that C is indeed a solution. Then, for each vertex in the graph, v ∈ V, I need to check if it is either in the given set v ∈ C, such as O(|𝑉|), or one of its edges has an endpoint in the set, which can be done in O(|𝑉| + |𝐸|) by hashing the vertex set and then looping over the set of edges. This work will take most O(|𝑉| + |𝐸|), which is the worst case. That is, the solution can be verified in poly-time. Thus, PYGMALION is in NP.
(3).Shows PYGMALION is in NP-Complete
I will use Vertex Cover
Step1. Show that Vertex-Cover(G, k) can be reduced to PYMALION(G’, k’), and that the reduction can be done in polynomial time:
A vertex cover is set of vertices such that for every edge in the graph, at least one of edge’s end points is in the vertex cover. In Vertex-Cover(G, k), I have a graph G = (V, E) and a target number k, and I need to find whether there exists is vertex cover of size at most k. Based on that, I can build the input for PYMALION(G’, k’); here, k’ = k. Now I will make new graph G’ = (V’, E’). First, G’ has all the edges and vertices of G. In addition, for every edge {u, v}∈ E, I will create a new vertex w and new edges {u, w} and {w, v} and place them in G’.
Initial graph G must be copied for the reduction; O(|𝑉| + |𝐸|). And for every edge, I need to add a new node (O(|𝐸|)) and create two new edges (O(|𝐸|)). Therefore, this takes poly-time: O(|𝑉| + |𝐸|).
Step2. Vertex-Cover(G, k) has a solution, iff the corresponding PYGMALION(G’, k’) has a solution:
⚫ Show Vertex-Cover(G, k) to PYGMALION(G’, k’):
Let S ∈ V be a vertex cover in G. I will show S is a valid solution for G’. First notice that if S is a vertex cover, then this implies that for every edge in G, at least one of its endpoints is in S. Now consider some vertex x in G’ such as x ∈ V′.
(a).If x is an original vertex in G, then either x ∈ S or there must exist some edge in G which connects x to some vertex u ∈ S. Thus, x either has a bunker (x ∈ S), or x is a connected to some vertex u which has a bunker (u ∈ S).
(b).If x is not in G, then it forms a triangle with two adjacent vertices u, v in G. The triangle is composed of three edges: (i, x), (x, v), and (u, v). Where, edge (u, v) is in G. Therefore, it must be covered by S which contain at least one of u or v. Vertex x is connected to by an edge to a vertex belonging to S. That is, x is connected to some vertex which has bunker.
Thus, if G has a vertex cover S, then S is also a solution to PYGMALION(G’, k’), k =k’ = |𝑆|.
⚫ Show PYGMALION(G’, k’) to Vertex-Cover(G, k):
Let D be a solution for G’ (|𝐷| = 𝑘′). Consider first the vertices w ∈ D which don’t correspond to an original vertex in G. And w must be connected to two vertices u, v in G. Thus, I can replace w by either u or v, while maintaining the size and validity of the solution. This is because u, v, and w form a triangle, and w connects only to u and v. Do it for all vertices w ∈ D that do not belong to the graph G, I can get a solution S (|𝑆| = |𝐷| = k′) which is a valid solution G’, however that only consists of vertices in the original graph G. It makes sure that the edge (u, v) is covered in G by either u, v, because every edge (u, v) creates a vertex x that must be covered in G’ by either u or v. Thus, all the additional vertices in G’ are covered by the solution S. which means that all edges in G are covered by S. Therefore, if G’ has a solution D, this can be converted, so a valid vertex cover for G of size at most k.
Step3. Thus, It is NP-Complete, because PYGMALION is in NP and has been shown to be at least as hard as Vertex-Cover.
Reference
http://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/bin_packing.pdf
CSE6140 lecture slide 11 (NP-Completeness-3)