Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018
DOI: 10.7155/jgaa.00511
Approximating Partially Bounded Degree Deletion on Directed Graphs
Vol. 23, no. 5, pp. 759-780, 2019. Regular paper.
Abstract The $\rm{B\small{OUNDED}}$ $\rm{D\small{EGREE}}$ $\rm{D\small{ELETION}}$ problem (BDD) is that of
computing a minimum
vertex set in a graph $G=(V, E)$ with degree bound $b:
V\rightarrow\mathbb{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+\ln
b_{\max}$ [Okun, Barak, IPL, 2003], where $b_{\max}$ is the maximum degree bound.
This paper considers BDD on directed graphs containing
unbounded vertices, which we call $\rm{P\small{ARTIAL}}$ $\rm{B\small{OUNDED}}$ $\rm{D\small{EGREE}}$ $\rm{D\small{ELETION}}$ (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+\max_{v\in
V}\ln(b^-(v)+b^+(v))$,
2) it becomes NP-hard to approximate PBDD better than $b_{\max}$
(even on undirected graphs) once unbounded vertices are
allowed, and 3) PBDD can be approximated within $\max\{2,b_{\max}+1\}$
when only in-degrees are partially bounded by $b$ (and the out-degrees
of all the vertices are unbounded).
|
Submitted: March 2018.
Reviewed: February 2019.
Revised: March 2019.
Accepted: March 2019.
Final: September 2019.
Published: October 2019.
|
Journal Supporters
|