On the Complexity of Making a Distinguished Vertex Minimum or Maximum Degree by Vertex Deletion

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