NP

Question 1

Clique is conceptually the opposite of ____

Answer 1

Independent Set

Question 2

Set of vertices S of an Independent Set of G is the equivalent to ____.

(with regard to cliques)

Answer 2

Same S of complementary graph for a clique.

“Can Luke Inspect Some Goods?”

Question 3

Definition of vertex cover

Answer 3

for every (x,y) ∈ E, either x ∈ S or y ∈ S

Question 4

What is the key claim regarding vertex cover –> I.S. NP reductions?

Answer 4

S is a vertex cover IFF S̄ is an independent set in the the same graph.

“Venture Capital Is So Sexy”

Question 5

If A –> B, what do we know about B?

Answer 5

That B is at least as hard as A

Question 6

NP complete is the intersection of…

Answer 6

NP and NP-Hard

Question 7

All NP-Complete problems are ____, but not all _____ are _____.

Answer 7

1. NP-Hard
2. NP-Hard
3. NP-Complete

Question 8

Vertex Cover –> Clique Lemma

Answer 8

Vertex cover S IFF complement of S is clique of complement of G.

Question 9

Relationship between #vertices, #edges in clique

Answer 9

|e| = k(k-1)/2

Question 10

Clique I/O

Answer 10

INPUT: Graph G and goal g

OUTPUT:

1. set of vertices S (clique) with size >= g if possible
2. NO otherwise

Question 11

Vertex Cover I/O

Answer 11

INPUT: graph G and budget b

OUTPUT:

1. set of vertices S (vertex cover) <= b if possible
2. NO otherwise

Question 12

Independent Set I/O

Answer 12

INPUT: graph G and goal g

OUTPUT:

1. set of vertices S (independent set) >= g if possible
2. NO otherwise