Options
Metric dimension parameterized by feedback vertex set and other structural parameters
Publikationstyp
Journal Article
Date Issued
2023
Sprache
English
Author(s)
Khazaliya, Liana
Inerney, Fionn
Volume
37
Issue
4
Start Page
2241
End Page
2264
Citation
SIAM Journal on Discrete Mathematics 37 (4): 2241-2264 (2023)
Publisher DOI
Scopus ID
Publisher
Society for Industrial and Applied Mathematics Publications
For a graph G, a subset S \subseteq V (G) is called a resolving set if for any two vertices u, v \in V (G), there exists a vertex w \in S such that d(w, u) \not= d(w, v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [M. R. Garey and D. S. Johnson, Computers and Intractability-A Guide to NP-Completeness, Freeman, San Francisco, 1979]. In the realm of parameterized complexity, Hartung and Nichterlein [28th Conference on Computational Complexity, IEEE, Piscataway, NJ, 2013, pp. 266-276] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is fixed parameter tractable (FPT) when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular, the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the pathwidth. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to cocluster, both of which are smaller parameters than the vertex cover number.
Subjects
feedback vertex set
FPT Algorithm
metric dimension
structural parameterization
W[1]-hardness
DDC Class
510: Mathematics