cispa_all_3782.pdf (780.55 kB)

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

conference contribution

posted on 2023-11-29, 18:22 authored by Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, Prafullkumar TaleFor a graph G, a subset S ⊆ V (G) is called a resolving set if for any two vertices u, v ∈ V (G), there
exists a vertex w ∈ S such that d(w, u) ̸= 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 [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 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 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 Metric Dimension does not admit a polynomial kernel under
this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the
parameter is the distance to clique. On the positive side, we show that 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.

## History

## Preferred Citation

Esther Galby, Liana Khazaliya, Fionn Inerney, Roohani Sharma and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In: MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS). 2022.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS)## Legacy Posted Date

2022-09-23## Open Access Type

- Green

## BibTeX

@inproceedings{cispa_all_3782, title = "Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters", author = "Galby, Esther and Khazaliya, Liana and Inerney, Fionn Mc and Sharma, Roohani and Tale, Prafullkumar", booktitle="{MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS)}", year="2022", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC