Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters


Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 322KB

Supplementary Material (public)
There is no public supplementary material available

Galby, E., Khazaliya, L., Inerney, F. M., Sharma, R., & Tale, P. (2022). Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. Retrieved from https://arxiv.org/abs/2206.15424.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1DDF-A
For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set}
if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such
that $d(w,u) \neq d(w,v)$. The {\sc 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~[GT~61 in Garey and Johnson's book]. In the realm of
parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the
problem is W[2]-hard when parameterized by the natural parameter $k$. They also
observed that it is FPT when parameterized by the vertex cover number and asked
about its complexity under \emph{smaller} parameters, in particular the
feedback vertex set number. We answer this question by proving that {\sc Metric
Dimension} is W[1]-hard when parameterized by the feedback vertex set number.
This also improves the result of Bonnet and Purohit~[IPEC 2019] which states
that the problem is W[1]-hard parameterized by the treewidth. Regarding the
parameterization by the vertex cover number, we prove that {\sc Metric
Dimension} does not admit a polynomial kernel under this parameterization
unless $NP\subseteq coNP/poly$. We observe that a similar result holds when the
parameter is the distance to clique. On the positive side, we show that {\sc
Metric Dimension} is FPT when parameterized by either the distance to cluster
or the distance to co-cluster, both of which are smaller parameters than the
vertex cover number.