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.
