License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.51
URN: urn:nbn:de:0030-drops-168496
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16849/
Go to the corresponding LIPIcs Volume Portal


Galby, Esther ; Khazaliya, Liana ; Mc Inerney, Fionn ; Sharma, Roohani ; Tale, Prafullkumar

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

pdf-format:
LIPIcs-MFCS-2022-51.pdf (0.8 MB)


Abstract

For 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.

BibTeX - Entry

@InProceedings{galby_et_al:LIPIcs.MFCS.2022.51,
  author =	{Galby, Esther and Khazaliya, Liana and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16849},
  URN =		{urn:nbn:de:0030-drops-168496},
  doi =		{10.4230/LIPIcs.MFCS.2022.51},
  annote =	{Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set}
}

Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI