Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs

Foucaud, F.; Mertzios, G.B.; Naserasr, R.; Parreau, A.; Valicov, P.

Abstract

We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restricted to interval graphs and permutation graphs. We prove that both decision problems are NP-complete, even for graphs that are at the same time interval graphs and permutation graphs and have diameter 2. While Locating-Dominating Set parameterized by solution size is trivially fixed-parameter-tractable, it is known that Metric Dimension is W[2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

Citation

Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016, August). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Munich, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
• Acceptance Date: Apr 28, 2015
• Online Publication Date: Aug 5, 2016
• Publication Date: Aug 5, 2016
• Deposit Date: May 21, 2015
• Publicly Available Date: Aug 5, 2017
• Print ISSN: 0302-9743
• Pages: 456-471
• Series Title: Lecture notes in computer science
• Series Number: 9224
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers.
• ISBN: 9783662531730
• DOI: https://doi.org/10.1007/978-3-662-53174-7_32
• Public URL: https://durham-repository.worktribe.com/output/1152441