我们研究了在弦图和区间图上寻找几何数的计算复杂性。设 $S$ 为图 $G$ 的一个顶点集，如果 $G$ 中的每个顶点都位于 $S$ 中某一对顶点之间的最短路径上，则称 $S$ 为一个\textit{几何集}。\textsc{最小几何集 (MGS)} 问题是寻找给定图的最小基数几何集。我们证明了对于弦图，当以其\emph{树宽}（等于其团数）为参数时，\textsc{最小几何集}是固定参数可处理的。这意味着对于固定的 $k$，$k$-树有多项式时间算法。然后，我们展示了\textsc{最小几何集}在区间图上是 NP-hard 的，从而回答了 Ekim 等人（LATIN, 2012）提出的问题，他们表明在适当的区间图上\textsc{最小几何集}是多项式时间可解的。由于区间图的约束性，我们设计了一种相当复杂的归约技术，以绕过其固有的线性结构，从而证明了后者的结果。
博主点评： 本文揭示了几何集在特定图类上的复杂性，尤其是通过固定参数可处理性与 NP-hard 性的对比，展示了图论问题的深度与广度。这种复杂性分析为后续算法设计提供了重要的理论基础，值得深入研究。