Please answer the following question correctly and do not copy from anywhere els
ID: 645073 • Letter: P
Question
Please answer the following question correctly and do not copy from anywhere else!
tell me how sure you are when you solve this
Please answer the following question correctly and do not copy from anywhere else! tell me how sure you are when you solve this 1. Show the Wrestlers Wedding Problem is NP-complete Instance : A set W = {w1, w2,. . ., wn} of professional wrestlers, a collection of un Ordered pairs T = {(wi, wj)|wi wj in w} where (wi, wj) in T means that the wrestlers wi and wj will attack each other if in the same room, and an integer K > 0. Question : Is there a wedding party of size K? (i.e., Is there a subset P subseteq W such that if wi in P and wj in P then (wi,wj) not in T.)Explanation / Answer
Yes there can be a wedding party of size 1. where (w1,w1) can be in the same room and thus can belong to T and also w1 belongs to P and it can be a subset of T