2013 · 38 citations · 12 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityDimension ReductionMetric GeometryParameterized AlgorithmsShortest Path AlgorithmsTime ComplexityApproximation ComplexityApproximation HardnessComputational Complexity Of Graph AlgorithmsHardnessParameterized ComplexityPolynomial Time ComplexityPolynomial-time AlgorithmsVertex Distance
The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u, w} if the distance (length of a shortest path) between v and u is different from the distance of v and w. We give a polynomial-time computable reduction from the Bipartite Dominating Set problem to Metric Dimension on maximum degree three graphs such that there is a one-to-one correspondence between the solution sets of both problems. There are two main consequences of this: First, it proves that Metric Dimension on maximum degree three graphs is W[2]-hard with respect to the parameter k. This answers an open question concerning the parameterized complexity of Metric Dimension posed by Lokshtanov [Dagstuhl seminar, 2009] and also by Diaz et al. [ESA'12]. Additionally, it implies that a trivial n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> -time algorithm cannot be improved to an n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(k)</sup> -time algorithm, unless the assumption FPT≠W[1] fails. Second, as Bipartite Dominating Set is inapproximable within o(log n), it follows that Metric Dimension on maximum degree three graphs is also inapproximable by a factor of o(log n), unless NP=P. This strengthens the result of Hauptmann et al. [JDA'12] who proved APX-hardness on bounded-degree graphs.
12
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Samir Khuller, Balaji Raghavachari, Azriel Rosenfeld · Discrete Applied Mathematics · 1996 · 808 citations
On the Metric Dimension of Cartesian Products of Graphs
José Cáceres, Carmen Hernando, Mercè Ferrater Mora et al. · SIAM Journal on Discrete Mathematics · 2007 · 474 citations · Full text