18 Questions
What is the definition of a vertex cover in an undirected graph G=(V,E)?
A subset of vertices such that every edge is incident to at least one of the vertices
Why do we typically want to find the minimum sized vertex cover?
Because it is the optimal solution to the vertex cover problem
What problem is reduced to vertex cover to show that vertex cover is NP-complete?
CLIQUE
What is the relationship between a clique of size k in G and a vertex cover of size |V| - k in G’?
A clique of size k in G exists if and only if a vertex cover of size |V| - k exists in G’
What is the purpose of approximation algorithms?
To get a solution close to the optimal solution of an optimization problem in polynomial time
What are the two conditions for an algorithm to be an α-approximation algorithm for an optimization problem?
The algorithm runs in polynomial time, and it produces a solution that is within a factor α of the optimal solution
What is a clique in an undirected graph?
A subset of vertices such that each pair is connected by an edge
Why do we focus on decision problems in our study of NP?
Because we can reduce optimization problems to a series of decision problems
How do we construct a graph when reducing 3-CNF SAT to CLIQUE?
By creating a vertex for each literal and connecting vertices if they come from different clauses, avoiding incompatibility
What is the goal when reducing 3-CNF SAT to CLIQUE?
To produce a graph such that satisfying a formula with k clauses is equivalent to finding a k-vertex clique
Why do we start at 3 when finding a clique of a certain size?
The question is not specified, but presumably it's because a clique of size 1 or 2 is trivial
What is the relationship between the Vertex Cover Problem and CLIQUE?
They are both NP-complete problems, related to finding a subset of vertices in a graph
What is a set cover of a set T?
Any collection of subsets of T whose union is T.
Is the solution produced by the algorithm always optimal for the Set Cover Problem?
No, it is within a factor of α of the optimal solution.
What is a vertex cover?
Not provided in the given text.
What is the difference between randomized Las Vegas algorithms and Monte Carlo algorithms?
Las Vegas algorithms have a correct output and a variable running time, while Monte Carlo algorithms have a deterministic running time and may produce incorrect outputs with some probability.
Is the optimal solution to the Set Cover Problem always unique?
No, as shown in the example, there can be multiple optimal solutions.
What is the characteristic of an α-approximation algorithm for a minimization problem?
The solution produced by the algorithm is within a factor of α of the optimal solution, where α < 1.
Study Notes
Vertex Cover Problem
- A vertex cover of an undirected graph G = (V, E) is a subset of vertices such that every edge is incident to at least one of the vertices.
- Typically, we're interested in finding the minimum-sized vertex cover.
Reducing CLIQUE to Vertex Cover
- To show vertex cover is NP-complete, we reduce CLIQUE to vertex cover.
- Given a graph G, we create a complement graph G' such that a clique of size k in G exists iff a vertex cover of size |V| - k exists in G'.
Approximation Algorithms
- Approximation algorithms are used to get a solution close to the optimal solution of an optimization problem in polynomial time.
- Definition: An algorithm is an α-approximation algorithm for an optimization problem Π if it runs in polynomial time and the algorithm always produces a solution that is within a factor of α of the optimal solution.
Reduction from 3-CNF SAT to CLIQUE
- Given a boolean formula in 3-CNF SAT, we produce a graph (in polynomial time) such that satisfying the formula with k clauses is equivalent to finding a k-vertex clique.
- For each clause, create a vertex for each literal, and connect vertices if they come from different clauses, avoiding incompatibility.
Decision Problems vs Optimization Problems
- Finding the maximum-sized clique is an optimization problem.
- We can reduce it to a series of decision problems (e.g., Can we find a clique of size 3?).
Set Cover (SC) Problem
- A set cover of a set T is any collection of subsets of T whose union is T.
- The set cover problem: given a weight for each subset, find the set cover that minimizes the total weight.
Vertex Cover vs Set Cover
- The red vertices are not a vertex cover in the given examples due to uncovered edges.
- A vertex cover is a subset of vertices such that every edge is incident to at least one of the vertices.
Randomized Algorithms
- Types of Randomized Algorithms:
- Randomized Las Vegas Algorithms: output is always correct, running time is a random variable.
- Randomized Monte Carlo Algorithms: output may be incorrect with some probability, running time is deterministic.
- Example: Randomized Quick Sort.
This quiz covers the vertex cover problem in undirected graphs, including finding the minimum sized vertex cover and proving its NP-completeness through reduction from the CLIQUE problem.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
