Hardness of Metric Dimension in Graphs of Constant Treewidth

作     者：Li, Shaohua Pilipczuk, Marcin 

作者机构：Univ Warsaw Inst Informat Warsaw Poland 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2022年第84卷第11期

页      面：3110-3155页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：European Research Council (ERC) under the European Union 

主　　题：Graph algorithms constant treewidth NP-hard 

摘      要：The METRIC DIMENSION problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S subset of V (G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of METRIC DIMENSION in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that METRIC DIMENSION is NP-hard in graphs of treewidth 24.