TY - JOUR

T1 - Approximating partially bounded degree deletion on directed graphs

AU - Fujito, Toshihiro

AU - Kimura, Kei

AU - Mizuno, Yuki

N1 - Publisher Copyright:
© 2019, Brown University. All rights reserved.

PY - 2019

Y1 - 2019

N2 - The Bounded Degree Deletion problem (BDD) is that of computing a minimum vertex set in a graph G=(V,E) with degree bound b: V → Z+, such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It is a classic problem in graph theory and various results have been obtained including an approximation ratio of 2+lnbmax [30], where bmax is the maximum degree bound. This paper considers BDD on directed graphs containing unbounded vertices, which we call Partially Bounded Degree Deletion (PBDD). Despite such a natural generalization of standard BDD, it appears that PBDD has never been studied and no algorithmic results are known, approximation or parameterized. It will be shown that (1) in case all the possible degrees are bounded, in-degrees by b− and out-degrees by b+, BDD on directed graphs can be approximated within 2+maxv ϵVln(b−(v)+b+(v)), and (2) although it becomes NP-hard to approximate PBDD better than bmax (even on undirected graphs) once unbounded vertices are allowed, it can be within max-2,bmax+1} when only in-degrees (and none of out-degrees) are partially bounded by b (and the out-degrees of all the vertices are unbounded).

AB - The Bounded Degree Deletion problem (BDD) is that of computing a minimum vertex set in a graph G=(V,E) with degree bound b: V → Z+, such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It is a classic problem in graph theory and various results have been obtained including an approximation ratio of 2+lnbmax [30], where bmax is the maximum degree bound. This paper considers BDD on directed graphs containing unbounded vertices, which we call Partially Bounded Degree Deletion (PBDD). Despite such a natural generalization of standard BDD, it appears that PBDD has never been studied and no algorithmic results are known, approximation or parameterized. It will be shown that (1) in case all the possible degrees are bounded, in-degrees by b− and out-degrees by b+, BDD on directed graphs can be approximated within 2+maxv ϵVln(b−(v)+b+(v)), and (2) although it becomes NP-hard to approximate PBDD better than bmax (even on undirected graphs) once unbounded vertices are allowed, it can be within max-2,bmax+1} when only in-degrees (and none of out-degrees) are partially bounded by b (and the out-degrees of all the vertices are unbounded).

UR - http://www.scopus.com/inward/record.url?scp=85078235744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078235744&partnerID=8YFLogxK

U2 - 10.7155/jgaa.00511

DO - 10.7155/jgaa.00511

M3 - Article

AN - SCOPUS:85078235744

SN - 1526-1719

VL - 23

SP - 759

EP - 780

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 5

ER -