In this paper we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph $G=(V,E)$, and two positive integers $D$ and $B$, the \emph{Minimum-Cardinality-Bounded-Diameter Edge Addition} (MCBD) problem is to find a minimum cardinality set $F$ of edges to be added to $G$ in such a way that the diameter of $G+F$ is less than or equal to $D$, while the \emph{Bounded-Cardinality-Minimum-Diameter Edge Addition} (BCMD) problem is to find a set $F$ of $B$ edges to be added to $G$ in such a way that the diameter of $G+F$ is minimized. Both problems are well known to be \np-hard, as well as approximable within $O(\log n \log D)$ and $4+2/D^*$, respectively, where $D^*$ denotes the diameter of an optimal solution for the BCMD problem. In this paper, we improve these long-standing approximation ratios to $O(\log n)$ and to $2+2/D^*$, respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within $c \log n$, for some constant $c>0$, unless $\p=\np$. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a factor of $\frac{5}{3}-\epsilon$, for some $\epsilon>0$. On the other hand, on the positive side, we show that twice of the minimal number of edges suffice to get at most twice of the required diameter.
Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems
D. Bilò;PROIETTI, GUIDO
2010-01-01
Abstract
In this paper we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph $G=(V,E)$, and two positive integers $D$ and $B$, the \emph{Minimum-Cardinality-Bounded-Diameter Edge Addition} (MCBD) problem is to find a minimum cardinality set $F$ of edges to be added to $G$ in such a way that the diameter of $G+F$ is less than or equal to $D$, while the \emph{Bounded-Cardinality-Minimum-Diameter Edge Addition} (BCMD) problem is to find a set $F$ of $B$ edges to be added to $G$ in such a way that the diameter of $G+F$ is minimized. Both problems are well known to be \np-hard, as well as approximable within $O(\log n \log D)$ and $4+2/D^*$, respectively, where $D^*$ denotes the diameter of an optimal solution for the BCMD problem. In this paper, we improve these long-standing approximation ratios to $O(\log n)$ and to $2+2/D^*$, respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within $c \log n$, for some constant $c>0$, unless $\p=\np$. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a factor of $\frac{5}{3}-\epsilon$, for some $\epsilon>0$. On the other hand, on the positive side, we show that twice of the minimal number of edges suffice to get at most twice of the required diameter.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
