The Best Independent Set problem is defined as follows: Input: An undirected graph G, in which...

 

Transcribed Image Text:

The "Best Independent Set" problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value; and a target value T. Goal: A set of vertices S such that (a) no two vertices in S are connected by an edge in G; and (b) the total value of the vertices in S is at least T. For instance, in Graph 1 below, with T = 16, there are three solutions: { C,D }, { A,E }, and {B,E } In Graph 2, with T = 21 the only solution is { G,H,K} B5 A 3 D 10 E 13 Graph 1 C6 H 7 F K 2 8 Graph 2 The N-Queens problem is actually a special case of this, with the vertices being the squares on the chess board, an edge between two vertices if the squares attack, all vertices have value 1, and the target value is N. Problem 3 A. Describe an instance of Best Independent Set where doing a breadth-first search will construct 1000 (or more) times as many states as doing a depth-first search. B. Describe an instance of Best Independent Set where doing a depth-first search will construct 1000 (or more) times as many states as doing a breadth-first search. (Hint: There is an instance where the correct solution contains only one vertex.) The "Best Independent Set" problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value; and a target value T. Goal: A set of vertices S such that (a) no two vertices in S are connected by an edge in G; and (b) the total value of the vertices in S is at least T. For instance, in Graph 1 below, with T = 16, there are three solutions: { C,D }, { A,E }, and {B,E } In Graph 2, with T = 21 the only solution is { G,H,K} B5 A 3 D 10 E 13 Graph 1 C6 H 7 F K 2 8 Graph 2 The N-Queens problem is actually a special case of this, with the vertices being the squares on the chess board, an edge between two vertices if the squares attack, all vertices have value 1, and the target value is N. Problem 3 A. Describe an instance of Best Independent Set where doing a breadth-first search will construct 1000 (or more) times as many states as doing a depth-first search. B. Describe an instance of Best Independent Set where doing a depth-first search will construct 1000 (or more) times as many states as doing a breadth-first search. (Hint: There is an instance where the correct solution contains only one vertex.)

Answer rating: 100% (QA)

Based on the context provided the Best Independent Set problem is an optimization problem where the goal is to find a set of vertices in a graph such ... View the full answer