On approximating the maximum diameter ratio of graphs (Q1349101)

It is shown that the problem of determining the maximum diameter ratio (local density) \(\text{dr}(G)\) of a graph \(G\) is APX-complete, i.e. there is a polynomial time approximation algorithm which approximates \(\text{dr}(G)\) within factor 2 but there is a constant \(c> 1\) such that finding approximations within factor \(c\) from the optimum is NP-hard. The authors also prove that for every fixed integer \(d\geq 1\), finding a subgraph \(H\) of \(G\) with maximum number of vertices whose diameter is \(\leq d\) is polynomially equivalent to the MAX CLIQUE problem. If \(d\) is the diameter and \(n\) is the number of vertices of a given tree \(T\) then computing \(\text{dr}(T)\) can be implemented in time \(O(dn)\).