Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

DOI10.1137/22M1510911MaRDI QIDQ6072291zbMATH OpenFDO

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)

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)

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.

Cites work

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

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)