Question 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. 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.