# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2206.15424.pdf

(Preprint), 322KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.