A complete weighted graph \(G= (V, E, w)\) is called \(\Delta _{\beta }\) -metric, for some \(\beta \ge 1/2\) , if G satisfies the \(\beta\) -triangle inequality, i.e., \(w(u,v) \le \beta \cdot (w(u,x) + w(x,v))\) for all vertices \(u,v,x\in V\) . Given a \(\Delta _{\beta }\) -metric graph \(G=(V, E, w)\) , the \(\Delta _{\beta }\) -Weighted Densest k-Subgraph ( \(\Delta _{\beta }\) -WDkS) problem is to find an induced subgraph G[C] with exactly k vertices such that the total edge weight of G[C] is maximized. For \(\beta = 1\) , this problem, \(\Delta\) -WDkS, is known NP-hard and admits a \(\frac{1}{2}\) -approximation algorithm. In this paper, we show the NP-hardness and the inapproximability of the \(\Delta _{\beta }\) -WDkS problem for any \(\beta> 1/2\) . We prove that \(\Delta _{\beta }\) -WDkS can be approximated to within a factor \((\frac{1}{2\beta }+\frac{2\beta -1}{2\beta \cdot (2k-3)})\) for any \(\beta> \frac{1}{2}\) and show that the analysis of the approximation ratio is asymptotically tight. Additionally, we describe a method to adapt any \(\alpha\) -approximation algorithm for \(\Delta\) -WDkS to obtain a \(\delta _{\alpha ,\beta }\) -approximation algorithm for \(\Delta _{\beta }\) -WDkS with \(\delta _{\alpha ,\beta }> \alpha\) for every \(\beta <1\) . This allows for improved approximations for \(\Delta _{\beta }\) -WDkS instances, offering potential enhancements to existing algorithms for this problem.
