Foucaud, F. and Mertzios, G.B. and Naserasr, R. and Parreau, A. and Valicov, P. (2016) 'Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.', Algorithmica., 78 (3). pp. 914-944.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (634Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1007/s00453-016-0184-1 |
| Publisher statement: | The final publication is available at Springer via https://doi.org/10.1007/s00453-016-0184-1 |
| Date accepted: | 06 July 2016 |
| Date deposited: | 02 September 2016 |
| Date of first online publication: | 14 July 2016 |
| Date first made open access: | 14 July 2017 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
