Algorithm Design ECS 122A
Popular in Course
Popular in Engineering Computer Science
This 2 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 122A at University of California - Davis taught by Zhaojun Bai in Fall. Since its upload, it has received 156 views. For similar materials see /class/187716/ecs-122a-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Algorithm Design
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/08/15
ECS122A Handout June 2 2009 How to prove a problem is NP complete Example 1 The directed Hamilton cycle HC problem is known to be NP complete In the following we show that the directed HC problem is reducible to the undirected Hamilton cycle problem Therefore we conclude that the undirected HC problem is also NP complete PROOF Let G V E be a directed graph with n vertices G is transformed into the undirected graph G V E by the transform function T de ned as the following 1 E V 111112113 E V and 111112 112113 6 E and 1111 6 E A 113111 6 E Clearly T is polynomial time computable We now show that G has aHC ltgt G has aHC o gt Suppose that G has a directed HC 121122 vnv1 Then 1 2 3 1 2 3 1 2 3 1 U17U17U17U27U27U277UmUmUmU1 is an undirected HC for G u lt Suppose that G has an undirected HC the three vertices say 121122123 that correspond to one vertex from G must be traversed consecutively in the order 121122123 or 123122121 since 122 cannot be reached from any other vertex in G Since the other edges in G connect vertices with superscripts 1 or 3 if for any one triple the order of the superscripts is 1 2 3 then the order is 1 2 3 for all triples Otherwise it is 3 2 1 for all triples Since G is undirected we may assume that its Hamilton cycle is 1 2 3 1 2 3 1 2 3 1 2 3 111171111711117012701270127 7Uinvvin7Uinvvilvvilvvil Then WNW2 12 12 is a directed Hamilton cycle for G D Example 2 The subset sum problem is known to be NP complete7 In the following7 we show that the subset sum problem is reducible to the job scheduling with penalties problem Therefore7 we conclude that the problem of job scheduling with penalties is also NP complete PROOF Let 31 32 73 and C be an input for the subset sum problem we may assume that 21 si 2 C Let the input be transformed into the following input for the job scheduling problem ti pi8i f0r1 i n7 di C forlgign7 n k Esra i1 Clearly the transformation takes polynomial time Now we shows that Yes instance of the subset sum ltgt Yes instance of the job scheduling o gt suppose that the subset sum input produces a YES answer ie7 there is a subset J of N 17 27 771 such that Zia si C Then let 7139 be any permutation of N that causes all jobs with indices in J to be done before any job with indices in N7 J The rst lJl jobs are completed by their deadline since Zia t Zia si C and C is the deadline for all jobs Then the total penalty M n n n n PW 2PM t 2 PW 0 2 PW Z 3W 87quot C k j1 jJi1 jlJl1 HJHI 11 Thus the jobs can be done with total penalty k c lt77 Let 7139 be any schedule for the jobs with total penalty k Let m be largest such that m i1 ie7 m is the number ofjobs completed by the deadline C The penalty7 then7 is Z p7ri k3i 0 2 i1 im1 Since 25 pi si for all 1 g i g n we must have m 7L m TI 7L 2 2 PW 23W Z 3W 2 i1 im1 i1 im1 i1 and this can happen only if the inequalities in 1 and 2 are equalities Thus m 2 07 i1 so the objects with indices 7r17 7r27 77rm are a solution to the subset sum problem D