Advanced Algorithms Quiz 2: 3 August 2025 (May 2025 term)

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

Consider the following algorithm for finding a smallest-sized subset of vertices $S \subseteq V(G)$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. To begin with, let $H = G$ and $S = \emptyset$. While $H$ has an induced path on 3 vertices $\{u, v, w\}$,we update $H$ to $H \backslash \{u, v, w\}$ and $S$ to $S \cup \{u, v, w\}$.We repeat this process until $H$ has no induced path on 3 vertices. What can we say about $k$, the size of the set $S$ output by this algorithm, relative to $k^\star$, the size of the optimal solution?

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, we can immediately return NO.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

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.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

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.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

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.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

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.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

DISJOINT CLUSTER VERTEX DELETION is NP-hard.

A graph is called a cluster graph if and only if it is a disjoint union of cliques.

The CLUSTER VERTEX DELETION (CVD) problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION (DCVD) problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph and the subgraph $G[S]$ is also a cluster graph. Our goal is to determine if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Answer the given subquestions about CVD and DCVD.

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

$\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}$

2: $C \leftarrow \{v_i \in V : x_i \geq 1/2\}$

3: return $C$

Based on the above data, answer the given subquestions.

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

$\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}$

2: $C \leftarrow \{v_i \in V : x_i \geq 1/2\}$

3: return $C$

Based on the above data, answer the given subquestions.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 2 shows a valid intermediate instance in the reduction with k= 2.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 3 shows a valid intermediate instance in the reduction with k= 2.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 2.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 5 shows a valid intermediate instance in the reduction with k= 2.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 1.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

The graph in Figure 1 has a FVS disjoint from S of size 2.

In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

The graph in Figure 1 has a FVS disjoint from S of size 1.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n= 4, calculate the number of sequences of length 4 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n = 5, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.