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
2012-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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11697/17052
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 44
  • ???jsp.display-item.citation.isi??? 33
social impact