Alternative parameterizations of \textsc{Metric Dimension}

DOI10.1016/J.TCS.2019.01.028MaRDI QIDQ2285127zbMATH OpenOpenAlexWikidataFDO

Authors G. Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractablegraphkernelmetric dimension

Mathematics Subject Classification ID

Distance in graphs (05C12) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: A set of vertices $W$ in a graph $G$ is called resolving if for any two distinct $x,yinV(G)$, there is $vinW$ such that ${mdist}_G(v,x)eq{mdist}_G(v,y)$, where ${mdist}_G(u,v)$ denotes the length of a shortest path between $u$ and $v$ in the graph $G$. The metric dimension $mmd(G)$ of $G$ is the minimum cardinality of a resolving set. The Metric Dimension problem, i.e. deciding whether $mmd(G)lek$, is NP-complete even for interval graphs (Foucaud et al., 2017). We study Metric Dimension (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by $k$ was proved to be $W[2]$-hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i.e., the problem of whether $mmd(G)len-k,$ where $n$ is the order of $G$. We prove that the dual parameterization admits (a) a kernel with at most $3k^4$ vertices and (b) an algorithm of runtime $O^{\ast }(4^{k+o(k)}).$ Hartung and Nichterlein (2013) also observed that Metric Dimension is fixed-parameter tractable when parameterized by the vertex cover number $vc(G)$ of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by $vc(G)+k$. Our reduction also gives evidence for non-existence of polynomial Turing kernels.

Recommendations

• Metric dimension parameterized by treewidth
• scientific article; zbMATH DE number 7650213
• Metric dimension of bounded width graphs
• Metric Dimension of Bounded Tree-length Graphs
• On the Complexity of Metric Dimension

Cites work

• (Non-)existence of polynomial kernels for the test cover problem
• A completeness theory for polynomial (Turing) kernelization
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Almost 2-SAT is fixed-parameter tractable
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Complexity of metric dimension on planar graphs
• Computing the metric dimension for chain graphs
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 5605062 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 4070955 (Why is no real title available?)
• 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?)
• scientific article; zbMATH DE number 2080246 (Why is no real title available?)
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Kernelization -- preprocessing with a guarantee
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Kernelization using structural parameters on sparse graph classes
• Kernelization. Theory of parameterized preprocessing
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Landmarks in graphs
• Metric Dimension of Bounded Tree-length Graphs
• Metric dimension parameterized by max leaf number
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Notions of metric dimension of corona products: combinatorial and computational results
• Parameterized algorithms
• Parameterized study of the test cover problem
• Partially polynomial kernels for set cover and test cover
• Recent developments in kernelization: a survey
• Resolvability in graphs and the metric dimension of a graph
• Solving MAX-\(r\)-SAT above a tight lower bound
• The (weighted) metric dimension of graphs: hard and easy cases
• The difference between the metric dimension and the determining number of a graph
• The metric dimension of the lexicographic product of graphs
• The NP-completeness of the bandwidth minimization problem

Cited in

(15)

• Metric dimension parameterized by treewidth
• Hardness of metric dimension in graphs of constant treewidth
• On vertices contained in all or in no metric basis
• On the status sequences of trees
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Metric dimension parameterized by max leaf number
• Metric dimension of bounded width graphs
• On metric dimensions of hypercubes
• scientific article; zbMATH DE number 7650213 (Why is no real title available?)
• Sharp bound on the truncated metric dimension of trees
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• Parameterized algorithms for locating-dominating sets
• Identifying codes in triangle-free graphs of bounded maximum degree
• Metric dimension and geodetic set parameterized by vertex cover

This page was built for publication: Alternative parameterizations of \textsc{Metric Dimension}

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