Metric Dimension of Bounded Tree-length Graphs

DOI10.1137/16M1057383zbMATH Open1371.68103arXiv1602.02610OpenAlexW2963994673MaRDI QIDQ5268001FDOQ5268001

Authors: Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan 

Publication date: 14 June 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The notion of resolving sets in a graph was introduced by Slater (1975) and Harary and Melter (1976) as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices x and y there is a vertex in the set which has distinct distances to x and y. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud et al. (2015) showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph.

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

Recommendations

• Metric dimension of bounded width graphs
• The metric dimension and girth of graphs
• scientific article; zbMATH DE number 7680433
• On the metric dimension of a graph
• Truncated metric dimension for finite graphs
• scientific article; zbMATH DE number 6739348
• Hardness of metric dimension in graphs of constant treewidth
• Metric dimension of directed graphs
• scientific article; zbMATH DE number 5844285

zbMATH Keywords

data structuresgraph algorithmsparameterized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Treewidth for graphs with small chordality
• Resolvability in graphs and the metric dimension of a graph
• Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
• Title not available (Why is that?)
• Parameterized Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transitiv orientierbare Graphen
• Treewidth. Computations and approximations
• Landmarks in graphs
• On the Complexity of Metric Dimension
• Parameterized Algorithms for Modular-Width
• On the complexity of computing treelength
• A survey of the algorithmic aspects of modular decomposition
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Title not available (Why is that?)
• Tree-decompositions with bags of small diameter
• Metric Dimension Parameterized by Max Leaf Number
• The (weighted) metric dimension of graphs: hard and easy cases

Cited In (22)

• Tree-Like Structures in Graphs: A Metric Point of View
• Metric properties of generalized Sierpiński graphs over stars
• Getting linear time in graphs of bounded neighborhood diversity
• On the complexity of computing treebreadth
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Metric dimension parameterized by treewidth
• Title not available (Why is that?)
• Alternative parameterizations of \textsc{Metric Dimension}
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Metric Dimension Parameterized by Treewidth in Chordal Graphs
• On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
• Local metric dimension for graphs with small clique numbers
• Parameterized Complexity of Geodetic Set
• Parameterized Complexity of Geodetic Set
• Treelength of series-parallel graphs
• Sequential metric dimension
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Hardness of metric dimension in graphs of constant treewidth
• Pathlength of outerplanar graphs
• Parameterized complexity for iterated type partitions and modular-width

This page was built for publication: Metric Dimension of Bounded Tree-length Graphs

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