  In this paper, we investigate the approximability of two node deletion
problems. Given a vertex weighted graph $G=(V,E)$ and a specified, or
"distinguished" vertex $p \in V$, MDD(min) is the problem of finding a minimum
weight vertex set $S \subseteq V\setminus \{p\}$ such that $p$ becomes the
minimum degree vertex in $G[V \setminus S]$; and MDD(max) is the problem of
finding a minimum weight vertex set $S \subseteq V\setminus \{p\}$ such that
$p$ becomes the maximum degree vertex in $G[V \setminus S]$. These are known
$NP$-complete problems and have been studied from the parameterized complexity
point of view in previous work. Here, we prove that for any $\epsilon > 0$,
both the problems cannot be approximated within a factor $(1 - \epsilon)\log
n$, unless $NP \subseteq DTIME(n^{\log\log n})$. We also show that for any
$\epsilon > 0$, MDD(min) cannot be approximated within a factor $(1
-\epsilon)\log n$ on bipartite graphs, unless $NP \subseteq DTIME(n^{\log\log
n})$, and that for any $\epsilon > 0$, MDD(max) cannot be approximated within a
factor $(1/2 - \epsilon)\log n$ on bipartite graphs, unless $NP \subseteq
DTIME(n^{\log\log n})$. We give an $O(\log n)$ factor approximation algorithm
for MDD(max) on general graphs, provided the degree of $p$ is $O(\log n)$. We
then show that if the degree of $p$ is $n-O(\log n)$, a similar result holds
for MDD(min). We prove that MDD(max) is $APX$-complete on 3-regular unweighted
graphs and provide an approximation algorithm with ratio $1.583$ when $G$ is a
3-regular unweighted graph. In addition, we show that MDD(min) can be solved in
polynomial time when $G$ is a regular graph of constant degree.
