Consider the statements about randomized quicksort and answer the given subquestions if they
are true or false.
An adversary can provide randomized quicksort with an input array of length
that forces the
algorithm to run in
time on that input. (If you are not familiar with the
asymptotic
notation, it roughly translates as “at least”. For example, we can say that it is possible to come up
with an input that forces insertion sort to run for
steps.)
6406536646566.
True
6406536646567.
False
A published solution is not available for this question yet.
Consider the following approximation algorithm for the weighted vertex cover problem:
1. Solve the relaxed linear program corresponding to the given problem:
**Minimize**
**Subject to**
2.
3. return
Based on the above data, answer the given subquestions.
Suppose that instead of putting a vertex
into the cover when
, we put
into the cover
when
. What happens?
6406536646574.
We still get a valid solution, and the algorithm remains a 2-approximation.
6406536646575.
We still get a valid solution, and the algorithm becomes a 4-approximation.
6406536646576.
We may no longer get a valid solution.
A published solution is not available for this question yet.
Consider the following approximation algorithm for the weighted vertex cover problem:
1. Solve the relaxed linear program corresponding to the given problem:
**Minimize**
**Subject to**
2.
3. return
Based on the above data, answer the given subquestions.
Suppose that instead of putting a vertex
into the cover when
, we put
into the cover
when
. What happens?
6406536646577.
We still get a valid solution, and the algorithm remains a 2-approximation.
6406536646578.
We still get a valid solution, and the algorithm becomes a
-approximation.
6406536646579.
We may no longer get a valid solution.
A published solution is not available for this question yet.
Consider the following approximation algorithm for the weighted vertex cover problem:
1. Solve the relaxed linear program corresponding to the given problem:
**Minimize**
**Subject to**
2.
3. return
Based on the above data, answer the given subquestions.
Suppose that we modify the algorithm to include vertex
in the cover only when
. What
happens?
6406536646580.
We still get a valid solution, and the algorithm remains a 2-approximation.
6406536646581.
We may no longer get a valid solution.
6406536646582.
We get an optimal solution always.
A published solution is not available for this question yet.
Consider the following approximation algorithm for the weighted vertex cover problem:
1. Solve the relaxed linear program corresponding to the given problem:
**Minimize**
**Subject to**
2.
3. return
Based on the above data, answer the given subquestions.
Suppose that we include vertex
in the cover when
. What happens?
6406536646583.
We always get a valid solution, but the approximation factor may become
worse.
6406536646584.
We always get an optimal solution.
6406536646585.
We may not get a valid solution.
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to
at least two vertices in S which are in different cliques, then we can delete it and leave the
parameter unchanged.
6406536646592.
True
6406536646593.
False
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to
at least two vertices in S which are in different cliques, then we can delete it and decrease the
parameter by 1.
6406536646594.
True
6406536646595.
False
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to
some but not all vertices in a clique of G[S], then we can delete it and leave the parameter
unchanged.
6406536646596.
True
6406536646597.
False
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to
some but not all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.
6406536646598.
True
6406536646599.
False
A published solution is not available for this question yet.
In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given
by the boxed vertices:
S := {a, c, e}
We need to find a **DISJOINT FVS** of size 2.
For each of the given statements, determine whether it is **True** or **False**.
Based on the above data, answer the given subquestions.
According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance
in the reduction with
.
6406536646608.
True
6406536646609.
False
A published solution is not available for this question yet.
In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given
by the boxed vertices:
S := {a, c, e}
We need to find a **DISJOINT FVS** of size 2.
For each of the given statements, determine whether it is **True** or **False**.
Based on the above data, answer the given subquestions.
According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance
in the reduction with
.
6406536646610.
True
6406536646611.
False
A published solution is not available for this question yet.
In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given
by the boxed vertices:
S := {a, c, e}
We need to find a **DISJOINT FVS** of size 2.
For each of the given statements, determine whether it is **True** or **False**.
Based on the above data, answer the given subquestions.
According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance
in the reduction with
.
6406536646612.
True
6406536646613.
False
A published solution is not available for this question yet.
In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given
by the boxed vertices:
S := {a, c, e}
We need to find a **DISJOINT FVS** of size 2.
For each of the given statements, determine whether it is **True** or **False**.
Based on the above data, answer the given subquestions.
According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance
in the reduction with
.
6406536646614.
True
6406536646615.
False
A published solution is not available for this question yet.
