On approximation algorithm for the edge metric dimension problem (Q2220845)

This article studies the concept of edge metric dimension. One can define the edge metric dimension as the smallest size of a vertex subset of a graph such that, for each pair of edges in the graph, there is a vertex in the subset which ``distinguishes'' the edges. Here, we say that two edges are distinguished by a vertex if they have different distances to the vertex (where the distance of an edge to a vertex is defined as the smaller of the two distances of its endpoints to the vertex). The analogous problem of vertex metric dimension (i.e., distinguishing vertices by distances) is a classical problem which has been well studied from both a graph-theoretical and an algorithmic point of view, with approximation algorithms and hardness of approximation results matching the ratio up to a multiplicative constant. As mentioned above, this work studies a natural edge metric dimension problem in which research interest has not been very pronounced and, in particular, for which approximability results are lacking. The main result of this work consists in claiming a \(1+\ln(n) + \ln(\log_2(n))\)-approximation algorithm for this problem. While the work uses standard techniques from submodular optimization, the result it mentions is nonetheless interesting. However, the quality of writing is substandard, and there are issues with the proofs. The most substantial ones I noticed are the following: \begin{itemize} \item In Case 2 in the proof of Lemma 2.5 the authors assume there are vertices \(x_1,x_2,...,x_k\) that split \(E_j\) into sets \(E_{j_1},...,E_{j_{k_j}}\), but one can find graphs where this does not hold, e.g., a tree consisting of 2 paths of length 3 sharing a single (root) endpoint, \(\Gamma_0=\emptyset\), and \(v\) being a root. \item In the proof of Lemma 2.5, one needs to address why, without loss of generality, one can assume that \(t=2\). This is not obvious, and it needs to be shown formally. \item The statement of Lemma 2.7 is wrong, and one can find a counterexample for it. One should say that \(\Delta_v f(\Gamma)=0\) needs to hold for every vertex \(v\), and the proof needs to be completely rewritten. \end{itemize} These are only some of the issues I found, and in my opinion the paper should not have been published in this version.