Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

DOI10.1137/22M1510911arXiv2206.15424MaRDI QIDQ6072291

Author name not available (Why is that?)

Publication date: 13 October 2023

Published in: (Search for Journal in Brave)

Abstract: For a graph $G$, a subset $SsubseteqV(G)$ is called a emph{resolving set} if for any two vertices $u,vinV(G)$, there exists a vertex $winS$ such that $d(w,u)eqd(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 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 {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.

Full work available at URL: https://arxiv.org/abs/2206.15424

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072291)