Skip to main content

Research Repository

Advanced Search

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.

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


Authors

F. Foucaud

R. Naserasr

A. Parreau

P. Valicov



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 Mar 29, 2024
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

Files





You might also like



Downloadable Citations