dc.contributor.author Bonnet, Édouard dc.contributor.author Purohit, Nidhi dc.date.accessioned 2022-04-05T08:05:18Z dc.date.available 2022-04-05T08:05:18Z dc.date.created 2022-01-18T14:49:42Z dc.date.issued 2021 dc.identifier.issn 0178-4617 dc.identifier.uri https://hdl.handle.net/11250/2989805 dc.description.abstract A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The METRIC DIMENSION problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. METRIC DIMENSION has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of METRIC DIMENSION with respect to treewidth. We provide a first answer to the question. We show that METRIC DIMENSION parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving METRIC DIMENSION in time f(pw)no(pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl+Δ, where tl is the tree-length and Δ the maximum-degree of the input graph. en_US dc.language.iso eng en_US dc.publisher Springer en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title Metric Dimension Parameterized By Treewidth en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2021 The Author(s) en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 2 dc.identifier.doi 10.1007/s00453-021-00808-9 dc.identifier.cristin 1983761 dc.source.journal Algorithmica en_US dc.source.pagenumber 2606-2633 en_US dc.identifier.citation Algorithmica. 2021, 83 (8), 2606-2633. en_US dc.source.volume 83 en_US dc.source.issue 8 en_US
﻿

### Denne innførselen finnes i følgende samling(er)

Med mindre annet er angitt, så er denne innførselen lisensiert som Navngivelse 4.0 Internasjonal