Approximating Partially Bounded Degree Deletion on Directed Graphs

Toshihiro Fujito, Kei Kimura, Yuki Mizuno

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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+In bmax [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 and out-degrees by, BDD on directed graphs can be approximated within, 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 when only in-degrees (and none of out-degrees) are partially bounded by b.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 12th International Conference, WALCOM 2018, Proceedings
EditorsM. Sohel Rahman, Wing-Kin Sung, Ryuhei Uehara
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319751719
Publication statusPublished - 2018
Externally publishedYes
Event12th International Conference and Workshop on Algorithms and Computation, WALCOM 2018 - Dhaka, Bangladesh
Duration: Mar 3 2018Mar 5 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th International Conference and Workshop on Algorithms and Computation, WALCOM 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Approximating Partially Bounded Degree Deletion on Directed Graphs'. Together they form a unique fingerprint.

Cite this