== A set of vertices D in an undirected graph G = (V,E) is called a...

 

Transcribed Image Text:

== A set of vertices D in an undirected graph G = (V,E) is called a dominating set if N(D) = V where N(S) is a set of all neighbors of all vetices in the set S (i.e. VvE VuED [(u, v) E E]). In the Dominating Set problem, we are given an undirected graph G and a positive integer k, and we are asked to test whether there exists a dominating set of size at most k. - - - Give a brute force algorithms for dominating set. What is its runtime? To give a correct algorithm and its runtime bound you must answer the following questions: - [4] What is a certificate (=sequence of Os and 1s) length? [5] How is a bit (or a group of bits) interpreted by a verifier? i.e. if bit (group of bits) #i is 1 (has value 1... 1) then what does the verifier do? respectively what if it is 0 (if it is group need to explain for all possible values of the group of bits)? [3] How do you decide that the prospective certificate is indeed a solution to the problem (i.e. what is the condition of acceptance/rejection of a prospective certificate)? [2] what is the runtime of processing one prospective certificate - [3] How do you produce prospective certificates? - [3] How many certificates you need to generate? == A set of vertices D in an undirected graph G = (V,E) is called a dominating set if N(D) = V where N(S) is a set of all neighbors of all vetices in the set S (i.e. VvE VuED [(u, v) E E]). In the Dominating Set problem, we are given an undirected graph G and a positive integer k, and we are asked to test whether there exists a dominating set of size at most k. - - - Give a brute force algorithms for dominating set. What is its runtime? To give a correct algorithm and its runtime bound you must answer the following questions: - [4] What is a certificate (=sequence of Os and 1s) length? [5] How is a bit (or a group of bits) interpreted by a verifier? i.e. if bit (group of bits) #i is 1 (has value 1... 1) then what does the verifier do? respectively what if it is 0 (if it is group need to explain for all possible values of the group of bits)? [3] How do you decide that the prospective certificate is indeed a solution to the problem (i.e. what is the condition of acceptance/rejection of a prospective certificate)? [2] what is the runtime of processing one prospective certificate - [3] How do you produce prospective certificates? - [3] How many certificates you need to generate?