Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity

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

Abstract

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting 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). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), 914-944. https://doi.org/10.1007/s00453-016-0184-1

• Journal Article Type: Article
• Acceptance Date: Jul 6, 2016
• Online Publication Date: Jul 14, 2016
• Publication Date: Jul 14, 2016
• Deposit Date: Sep 1, 2016
• Publicly Available Date: Jul 14, 2017
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 78
• Issue: 3
• Pages: 914-944
• DOI: https://doi.org/10.1007/s00453-016-0184-1
• Public URL: https://durham-repository.worktribe.com/output/1375655