Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

DOI10.1137/22M1510911arXiv2206.15424MaRDI QIDQ6072291FDOQ6072291

Authors: Esther Galby, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale 

Publication date: 13 October 2023

Published in: SIAM Journal on Discrete Mathematics (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

FPT algorithmmetric dimensionfeedback vertex setstructural parameterization\textsf{W}[1-hardness]

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Algorithms in computer science (68W99)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• On a new class of codes for identifying vertices in graphs
• Parameterized algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear time algorithm for metric dimension of cactus block graphs
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Complexity of metric dimension on planar graphs
• Domination and location in acyclic graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Locating a robber with multiple probes
• Metric dimension parameterized by max leaf number
• Centroidal localization game
• Adaptive identification in graphs
• Localization game on geometric and planar graphs
• Centroidal bases in graphs
• Metric Dimension of Bounded Tree-length Graphs
• Sequential metric dimension
• Metric dimension parameterized by treewidth
• Computing a metric basis of a bipartite distance-hereditary graph
• Hardness of metric dimension in graphs of constant treewidth
• Alternative parameterizations of \textsc{Metric Dimension}
• Truncated metric dimension for finite graphs
• Low-dimensional representation of genomic sequences
• Metric dimension: from graphs to oriented graphs
• Parameterized complexity dichotomy for Steiner Multicut
• Exploring the gap between treedepth and vertex cover through vertex integrity

Cited In (1)

• Structural Parameterizations of Feedback Vertex Set

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)