Header menu link for other important links
X
On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
Published in Elsevier
2015
Volume: 33
   
Pages: 71 - 80
Abstract
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∈V, MDD(min) is the problem of finding a minimum weight vertex set S⊆V\{p} such that p becomes the minimum degree vertex in G[V\S]; and MDD(max) is the problem of finding a minimum weight vertex set S⊆V\{p} such that p becomes the maximum degree vertex in G[V\S]. These are known NP-complete problems and they have been studied from the parameterized complexity point of view in [1]. Here, we prove that for any ε>0, both the problems cannot be approximated within a factor (1-ε)log n, unless NP⊆Dtime(nlog log 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(nlog log n), and that for any ε>0, MDD(max) cannot be approximated within a factor (1/2-ε)log n on bipartite graphs, unless NP⊆Dtime(nlog 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. © 2015 Elsevier B.V.
About the journal
JournalData powered by TypesetJournal of Discrete Algorithms
PublisherData powered by TypesetElsevier
ISSN15708667
Open AccessYes
Concepts (13)
  •  related image
    Approximation algorithms
  •  related image
    Computational complexity
  •  related image
    Graphic methods
  •  related image
    Polynomial approximation
  •  related image
    Bipartite graphs
  •  related image
    CONSTANT DEGREE
  •  related image
    FACTOR APPROXIMATION ALGORITHMS
  •  related image
    Hardness of approximation
  •  related image
    NODE DELETION
  •  related image
    PARAMETERIZED COMPLEXITY
  •  related image
    Polynomial-time
  •  related image
    UNWEIGHTED GRAPHS
  •  related image
    Graph theory