标题： 在结构受限图中击中测地线区间 显示英文标题

标题： Hitting Geodesic Intervals in Structurally Restricted Graphs

摘要： 给定一个图$G = (V,E)$，一个顶点对集合$T$和一个整数$k$， Hitting Geodesic Intervals 询问是否存在一个大小至多为$k$的集合$S \subseteq V$，使得对于每个终端对$\{u,v\} \in T$，集合$S$与至少一条最短$u$-$v$路径相交。 阿拉文德和萨克塞纳 [WALCOM 2024] 引入了这个问题并展示了若干参数化复杂性结果。 在本文中，我们在负面和正面方向上扩展了已知的结果，并就结构图参数方面呈现了尖锐的复杂性对比。 我们首先表明，即使在通过向一个不相交的五顶点路径的并集中添加一个顶点得到的图上，这个问题也是NP难的。 通过修改这个结果的证明，我们还表明在通过向一条路径添加一个顶点得到的图上以及在通过向一个不相交的三角形的并集中添加一个全连接顶点得到的图上，该问题也是NP难的。 此外，我们通过将最后一个情况中的全连接顶点替换为一条长路径，证明了在带宽为4且最大度为5的图上，该问题也是NP难的。 在标准复杂性假设下，这些负面结果排除了大多数文献中研究的结构参数的固定参数算法（如果解的大小$k$不是参数的一部分）。 我们接下来提出了固定参数算法，参数分别为$k$加上模块宽度和$k$加上顶点完整性。 后一种情况的算法确实解决了一个更一般的设置，其中包括终端顶点的最小顶点多路切割大小的参数化。 我们证明这是紧致的，即以终端对的最小顶点多切分大小为参数的问题是 W[2]-完全的。 然后我们修改了这一不可解性结果的证明，并表明在某些情况下，该问题在参数为$k$时仍然是 W[2]-完全的，其中$T = \binom{Q}{2}$对于某些$Q \subseteq V$成立。 显示英文摘要

摘要： Given a graph $G = (V,E)$, a set $T$ of vertex pairs, and an integer $k$, Hitting Geodesic Intervals asks whether there is a set $S \subseteq V$ of size at most $k$ such that for each terminal pair $\{u,v\} \in T$, the set $S$ intersects at least one shortest $u$-$v$ path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size $k$ is not part of the parameter). We next present fixed-parameter algorithms parameterized by $k$ plus modular-width and by $k$ plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is W[2]-complete parameterized by $k$ even in the setting where $T = \binom{Q}{2}$ for some $Q \subseteq V$.