论文标题
w [1] - 由骨架维度参数参数的K-中心问题
W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension
论文作者
论文摘要
在$ k $ - 中心问题中，我们获得了一个图形$ g =（v，e）$，具有正边缘权重和一个整数$ k $，目标是选择$ k $中心dertices $ c \ subseteq v $，使得从任何顶点到最关键的中心顶点的最大距离。在一般图表上，问题是NP硬化，不能在小于$ 2 $的因素内近似。 $ k $ - 中心问题的典型应用可以在物流或城市规划中找到，因此很自然地研究运输网络上的问题。此类网络通常被表征为（几乎）平面或具有低倍维度，高速公路维度或骨架维度的图形。费尔德曼（Feldmann）和马克思（Marx）表明，当通过$ k $，高速公路尺寸$ hd $和路径放宽$ pw $参数化时，$ k $ center在恒定尺寸的平面图上是w [1] - hard。我们扩展了他们的结果并表明，即使我们还通过骨架尺寸$κ$进行参数化，$ k $ - 中心问题仍然存在[1] -hard。此外，我们证明，在指数时间假设下，对于$ k $ center来说，没有确切的算法，它具有运行时$ f（k，hd，pw，pw，κ）\ cdot \ cdot \ vert v \ vert v \ vert v \ vert^{o（pw+κ+κ+ \ \ \ \ \ \ sqrt {k+ hd}）$。
In the $k$-Center problem, we are given a graph $G=(V,E)$ with positive edge weights and an integer $k$ and the goal is to select $k$ center vertices $C \subseteq V$ such that the maximum distance from any vertex to the closest center vertex is minimized. On general graphs, the problem is NP-hard and cannot be approximated within a factor less than $2$. Typical applications of the $k$-Center problem can be found in logistics or urban planning and hence, it is natural to study the problem on transportation networks. Such networks are often characterized as graphs that are (almost) planar or have low doubling dimension, highway dimension or skeleton dimension. It was shown by Feldmann and Marx that $k$-Center is W[1]-hard on planar graphs of constant doubling dimension when parameterized by the number of centers $k$, the highway dimension $hd$ and the pathwidth $pw$. We extend their result and show that even if we additionally parameterize by the skeleton dimension $κ$, the $k$-Center problem remains W[1]-hard. Moreover, we prove that under the Exponential Time Hypothesis there is no exact algorithm for $k$-Center that has runtime $f(k,hd,pw,κ) \cdot \vert V \vert^{o(pw + κ+ \sqrt{k+hd})}$ for any computable function $f$.
