Metric Dimension of Bounded Tree-length Graphs

DOI10.1137/16M1057383zbMATH Open1371.68103OpenAlexW2963994673MaRDI 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
• On lower bounds for the metric dimension of graphs
• 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

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

Cited In (23)

• Tree-Like Structures in Graphs: A Metric Point of View
• Metric properties of generalized Sierpiński graphs over stars
• Parameterized complexity of geodetic set
• 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
• Metric dimension of bounded width graphs
• Local metric dimension for graphs with small clique numbers
• 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)