arXiv:2611.09733 · v1

Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth

首次提交 2026-11-07 01:09

版本更新 2026-11-07 01:09

雷达观测 2026-11-09 13:22

摘要

The metric dimension of a graph is the minimum size of a set of vertices whose distance vectors distinguish all vertices of the graph. We prove that \MetricDimension{} is NP-complete on planar graphs of treewidth and bag-connected treewidth exactly three. The graphs in our construction have no induced cycle longer than four and have (prefix-connected) pathwidth at most four. In particular, the problem admits no XP algorithm parameterized by bag-connected treewidth unless $\mathrm P=\mathrm{NP}$. This answers questions of Bonnet and Purohit and of Bousquet, Deschamps, and Parreau. We prove that the problem is fixed-parameter tractable when parameterized by bag-connected pathwidth.