Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430845 | Journal of Discrete Algorithms | 2015 | 10 Pages |
In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph G=(V,E)G=(V,E) and a specified, or “distinguished” vertex p∈Vp∈V, MDD(min) is the problem of finding a minimum weight vertex set S⊆V∖{p}S⊆V∖{p} such that p becomes the minimum degree vertex in G[V∖S]G[V∖S]; and MDD(max) is the problem of finding a minimum weight vertex set S⊆V∖{p}S⊆V∖{p} such that p becomes the maximum degree vertex in G[V∖S]G[V∖S]. These are known NPNP-complete problems and they have been studied from the parameterized complexity point of view in [1]. Here, we prove that for any ϵ>0ϵ>0, both the problems cannot be approximated within a factor (1−ϵ)logn(1−ϵ)logn, unless NP⊆Dtime(nloglogn)NP⊆Dtime(nloglogn). We also show that for any ϵ>0ϵ>0, MDD(min) cannot be approximated within a factor (1−ϵ)logn(1−ϵ)logn on bipartite graphs, unless NP⊆Dtime(nloglogn)NP⊆Dtime(nloglogn), and that for any ϵ>0ϵ>0, MDD(max) cannot be approximated within a factor (1/2−ϵ)logn(1/2−ϵ)logn on bipartite graphs, unless NP⊆Dtime(nloglogn)NP⊆Dtime(nloglogn). We give an O(logn)O(logn) factor approximation algorithm for MDD(max) on general graphs, provided the degree of p is O(logn)O(logn). We then show that if the degree of p is n−O(logn)n−O(logn), a similar result holds for MDD(min). We prove that MDD(max) is APXAPX-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.