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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
978-3-642-15154-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/32810
• ND
• ND
• ND