The Library
Alternative parameterizations of Metric Dimension
Tools
Gutin, Gregory, Ramanujan, M. S., Reidl, Felix and Wahlström, Magnus (2020) Alternative parameterizations of Metric Dimension. Theoretical Computer Science, 806 . pp. 133-143. doi:10.1016/j.tcs.2019.01.028 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2019.01.028
Abstract
A set of vertices W in a graph G is called resolving if for any two distinct , there is such that , where denotes the length of a shortest path between u and v in the graph G. The metric dimension of G is the minimum cardinality of a resolving set. The Metric Dimension problem, i.e. deciding whether , is NP-complete even for interval graphs (Foucaud et al., 2017). We study Metric Dimension (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by k was proved to be -hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i.e., the problem of whether , where n is the order of G. We prove that the dual parameterization admits (a) a kernel with at most vertices and (b) a randomized algorithm of runtime
⁎
. Hartung and Nichterlein (2013) also observed that Metric Dimension is fixed-parameter tractable when parameterized by the vertex cover number of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by , unless NP ⊆ coNP/poly. Our reduction also gives evidence for non-existence of polynomial Turing kernels. We also prove that Metric Dimension parameterized by bandwidth or cutwidth does not admit a polynomial kernel, unless NP ⊆ coNP/poly. Finally, using Eppstein's results (2015) we show that Metric Dimension parameterized by max-leaf number does admit a polynomial kernel.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Theoretical Computer Science | ||||||||
Publisher: | Elsevier Science BV | ||||||||
ISSN: | 0304-3975 | ||||||||
Official Date: | 2 February 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 806 | ||||||||
Page Range: | pp. 133-143 | ||||||||
DOI: | 10.1016/j.tcs.2019.01.028 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |