## 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)

## Reviews

There are no reviews yet.