论文标题
关于旅行销售人员问题的多项式内核及其概括
On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
论文作者
论文摘要
对于许多问题，实践的重要实例具有某些在特定算法设计中应反映的结构。由于数据降低是当今计算的重要且不可忽视的部分，因此我们采用了这种预启用的最成功模型之一 - 内核化。在此框架内，我们专注于旅行销售人员问题（TSP）及其一些概括。 我们为TSP提供具有大小多项式的TSP内核，无论是反馈边缘设置的数字还是调制器的大小到恒尺寸的组件。为了进行概括，我们还考虑了其他结构参数，例如顶点覆盖号和调制器的大小到恒定路径。我们通过证明多项式大小的内核相对于分数数，组合参数的最高度和树宽的存在来补充消极方面的结果，对于子集-TSP，不太可能在子集-TSP中，调制器对分离量（即，不可能脱离两个图）。
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today's computation, we employ one of the most successful models of such precomputation -- the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of Subset-TSP, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
