版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.