Finding Reductions in NP-Hardness Proofs
To find a polynomial-time many-one reduction from a known NP-hard decision problem A to a target problem B, ensure that the reduction maps inputs correctly such that the output for A is 'yes' if and only if the output for B is 'yes.' An example is demonstrated using Subgraph Isomorphism and Hamiltonian Cycle problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 2-4 How to find a reduction in proof of NP-hardness?
Goal Suppose that you already find a NP-hard decision problem A which seems close to target decision problem B. You want to find a polynomial-time many-one reduction f from A to B. This f should map inputs of A to inputs of B, satisfying that at input x, problem A outputs yes iff at input f(x), problem B outputs yes. How to find the construction of f? Analyze output!!!
Reduction Problem A Problem B construct inputs inputs such that outputs outputs yes yes no no
Find a Reduction Problem A Problem B construct inputs inputs find outputs outputs yes yes no no
Example 1: Subgraph Isomorphism Given two graphs and is , isomorphic to G G G 1 2 1 subgraph a of ? G 2 We want to use well-known NP-complete Hamiltonian Cycle problem: Given a graph G, does G contain a Hamitonian cycle?
Analysis Analysis Hamiltonian Cycle Subgraph Isomorphic construct inputs inputs Two Graphs and G G G = Graph ( , ) V E 1 2 find outputs outputs Yes: contains G Hamiltonia a cycle n subgraph a has G isomorphic to a cycle of size | | V Yes: isomorphic is 1 G = subgraph a to V of G G 2 if G a = cycle G of size | | 1 . 2
Reduction Reduction Hamiltonian Cycle Subgraph Isomorphic construct input = input G = a = cycle G of size | | G V Graph ( , ) V E 1 . G 2 outputs outputs Yes: contains G Hamiltonia a cycle n Yes: 1 is G isomorphic subgraph a to of G 2
Example 2: Example 2: = Given set a of positive n integers, { , ,..., is }, partition a there A a a a 1 2 n a a = | such that | . 2 A A A a a 1 2 A A 1 2 Consider t partition he problem : = Given set a of positive n integers, { , ,..., partition a there is }, A a a a 1 2 n a a = = such that . A A A a a 1 2 A A 1 2
Analysis Analysis Partition Example 2 construct inputs positive inputs positive integers a , ,..., integers a , ' 1 ' ,..., ' a n a a a 1 2 2 n find outputs outputs There a is partition ( , ' A ' ) A There a is partition ( , ) Yes: Yes: A A There a is partition ( , ) Yes: A A 1 2 1 2 1 2 a A a a a | a a = such that | . 2 a a = set ' 3 a a such that 3 3 . a a = such that . a a i i 1 ' ' A A A 2 A A 1 2 1 2 For every partition ( , ' A ' ), A For every partition ( , ), A A For every partition ( , ), A A No: No: No: 1 2 1 2 1 2 a A a a a a a | | | 3 . 2 a a | 3 3 . 3 a a = | | . 1 a a 1 ' ' A A A A A 2 1 2 1 2
Reduction Reduction Partition Example 2 construct input positive input positive integers a , ,..., integers 3 ,3 ,...,3 a n a a a n a 1 2 1 2 outputs outputs Yes: There a is partition ( , ) A A There a is partition ( , ' A ' ) A Yes: 1 2 1 2 a a a A a = such that . a a | such that | . 2 a a A A 1 ' ' A 1 2 2
Example 3: Knapsack Example 3: Knapsack + + + max c x c x c x 1 1 2 2 n n + + + s.t. s x c x s x ,..., S 1 1 2 2 n n 2 , 1 = } 1 , 0 { for x i n i Decision Version 2 , 1 = Given positive integers c , for ,..., , and , s i n S k i i solution a have system following does + + + c x c x c x k 1 1 2 2 n n + + + s x c x s x ,..., S 1 1 2 2 n n 2 , 1 = } 1 , 0 { for x i n i
Analysis Analysis Knapsack Partition construct inputs positive inputs positive 2 , 1 = integers a , ,..., integers c , for ,..., , and a n a s i n S k 1 2 i i find outputs outputs + + + suggests This s c = = to i set = a x a x a x k There a is partition ( , ) A A Yes: 1 1 2 2 n n 1 2 a a = = for + 2 , 1 + ,..., a + , a n + + + = a x a x a x k such that . a a i i i 1 1 2 2 n n A A ( / ) n . 2 S k a a 2 , 1 = 1 2 } 1 , 0 { for ,..., x i n 1 2 i solution w a has a k + = hen a + + ( / ) n . 2 a 1 2
Reduction Reduction Partition Knapsack construct input input positive = = = set S for + 2 , 1 a + ,..., , c s a i n i i i integers a , ,..., a n a = = + ( / ) n . 2 k a a 1 2 1 2 outputs outputs Yes: There a is partition ( , ) A A Yes: + + + a x a x a x k 1 2 1 1 2 2 n n a a = such that . a a + + + a x a x a x k 1 1 2 2 n n A A 1 2 2 , 1 = } 1 , 0 { for ,..., x i n i solution a has .
Example 4: Set Cover Example 4: Set Cover Given collection a of C subsets of X a finite set minimum a find , C X subcollect ion C of ' covering , every i.e., , element of C X appears in '. Decision Version Given collection a C of subsets of a finite set k integer an and , 0 C X k does subcollect a have ion of ' most at subsets covering , . C X
Analysis 1 To output yes, the set cover problem should find a subcollection of at most k subsets, covering X. The word cover may suggest us to select a NP-complete problem which have a similar output, the vertex-cover problem. Vertex-Cover (decision version): Given a graph G and an integer k>0, is G has a vertex cover of size at most k? Comparing two outputs, we would find following correspondence: vertex <-----> subset edge <-----> element
Reduction Reduction Vertex Cover Set Cover construct input input = set E edges all {{ X = Graph ( , integers and ) 0 G V E k = incident t o | } } C u u V = k k outputs outputs Yes: has a vertex cover G of Yes: subcollect a has ion of size , C covering k size k X
Analysis 2 Actually, the 3DM problem is a special case of the set cover problem (decision version). In this special case, given collection consists of subsets with special structure. 3DM Given thre : disjoint e sets , , each of elements, X collection a and Y X Y Z n C of 3 - sets each of which contains element an C of element an , of and element an of determine , C whether contains 3 a - dimensiona matching, l Y Z subcollect a i.e., ion of ' 3 - containing sets, elements all of . n X Z
Reduction Reduction 3DM Set Cover construct input input set X X Y Z = = = three disjoint sets , , with | | | | | | , X Y Z X Y Z n C C collection a and of 3 - containing each sets Y an C k n element of element an , of element an and of . X Z outputs outputs Yes: Yes: contains a set - cover of size . C n contains 3DM. a C
Example 5: Hamiltonian Path G = Given graph a ( , does ), contain G a V E Hamiltonia n path? It is natural to select the well-known NP-complete Hamiltonian Cycle problem.
Analysis If Hamiltonia a has G cycle, n then this cycle contains Hamiltonia a path. n However, if contain not may it then path, n Mamiltonia a has G Hamiltonia a n cycle. When Hamiltonia a path n can turn Hamiltonia a out cycle? n An idea is u split to node a of u into G two, and u together , ' u with edges all incident t o . Then Hamitonian a has G cycle if and only if the new Hamiltonia a has graph n path between and u Furthermor '. order to in e, make the new graph " if it has w u Hamiltonia a w path, n then the between is path and u '." put two we , horns ( , ) u u and ( , ' ). ' u 1v u ' u ' w w G kv
Solution Consider G input an graph of Hamiltonia the cycle n problem. Select any node G u of Split . into u two, u w and u together , ' u with edges all incident t o Moreover, . u add two edges ( , ) and ( , ' G where ), ' u and w are ' w two new nodes. The w obtained graph denoted is by . ' If Hamiltonia a has G cycle, n G then clearly, Hamiltonia a has ' path n between G and w Conversely '. w if , between be must path then this path, n Hamiltonia a has ' w u and w Delete '. w edges ( , ) and G ( , ' ) ' u and merge and u Then we '. would w u obtain Hamiltonia a cycle n of . 1v u ' u ' w w G kv
Example 6: Spanning with Min # of Leaves G = Given graph a ( , spanning a find ), tree with minimum number V E of leaves. Decision Version = Given graph a k ( , integer an and ) spanning a there is , 0 tree with G V E k most at of leaves.
Analysis A spanning tree with two leaves is exactly a Hamiltonian path. Therefore, we can give the same solution as that for the Hamiltonian path problem.
Example 7: Min Dominating Set G = Given graph a ( , minimum a find ), dominating set, i.e., a V E subset of verices such that every vert either is ex in the subset or adjacent t a o vertex in the subset. Decision Version = Given k graph a ( , integer an and ) dominating a does , 0 set of most at G V E k verices exist?
Analysis G = graph a In ( , every vert ), ex - dominating a is cover However, set. V E dominating a make order to In not true. is inverse the become set a vertex - cover, we may add a node on the middle of However, edge. each this new endpoints two blocks node of dominate to edge original each overcome To other. this trouble, we may put the original edge back. u u G ' G x uv v v
Solution = Considr input an graph v ( , ) of x uv Vertex the - Cover problem. G V E For each x uv edge v ( , create ), a node together G with two edges ( , ) u u x uv and ( , Then we ). obtain graph a . ' If has G a vertex - cover of size then the , same vertex set must k dominating a be set G for , ' also of size . G k Conversely , if dominating a has ' set E with D size x then with , D out loss k of x generality we , may v assume In . fact, if then we , can replace D uv either by D or u dominating a in results which , G x uv set of the same G size. uv Since dominates all in , ' covers D edges all in . E u u G ' G x uv v v
Example 8: Min Connected Dominating Set G = Given graph a ( , minimum a find ), connected dominating set, i.e., a V E subset of verices such that every vert either is ex in the subset adjacent t or o a moreover, and subset in the vertex this vertex subset induces connected a subgraph. Decision Version = Given graph a ( , integer an and ) k connected a does , 0 G V E k dominating set of most at verices exist?
Analysis u u u u y y G x x ' G x uv uv uv v v v v z z dominating make To 7. example in on constructi the from start We become set connected a dominating set, we may add an edge ( , connect and ) every to y y z node in . V Remember t hat edge ( , in ) order to in kept is E preserve that V dominate and v u u v u v each other. However, since dominate can y every node in u edge , ( , useless is ) Therefore, now. we may simplify graph deleting by ' ( , ). G v
z Solution Solution y u v x uv = Consider input an graph ( = , input an and ) integer 0 of Vertex the - Cover G V E k problem. Construct V = graph v u ' ( , ' y setting by ) ' E G V ' = { x ( | v , ) } { , and } z V x E uv ' {( k , ), ( , ( | ) uv , ) } {( , | ) u } {( , )}. E u x u v E y u V y z uv = . 1 + Set ' k If C has y a vertex - cover k of size then , connected a has ' dominating set G C k G { } of size . '
z continue continue y u v x uv Conversely , if connected a has ' dominating set of size then we , ' k have G D (a) must D contain (why?), y and without (b) loss of generality we , may D assume { \ } (why?). D y V easy to is it (b), and (a) From see that { \ a is } y vertex - cover of size in . k G
Example 9: Spanning with Max # of Leaves G = Given graph a ( , spanning a find ), tree with maximum number V E of leaves. Decision Version = Given graph a ( , integer an and ) spanning a there is , 0 tree G V E k with least at of leaves. k
Analysis spanning any For tree connected a in results leaves deleting , D dominating set. T connected a For dominating D V set construct , u a interestin tree nodes g in and D for each node \ add , an edge ( V , for ) some node Then we . D obtain u v v spanning a tree with nodes all in \ being D leaves. T Note that if a is D minimum connected dominating set, then T for the spanning constructe tree above, as d \ contains D leaves all of In . fact, if not, then V deleting leaves all of smaller a in result would connected dominating set. T Therefore, connected a has G dominating k V set of size if k and only if has G spanning a tree with least at | | leaves.
