论文标题
毛毛虫和加权路径的带宽参数复杂性
Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation
论文作者
论文摘要
在本文中，我们表明，对于{\ bf n} $中的所有$ t \的复杂性类别$ w [t] $也很难，即使对于具有三个头发长度的卡特彼尔（Caterpillars）也很难。 As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path $P_N$ and integer $M$, decide if there exists a mapping of the vertices of $P_N$ to a path $P_M$, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the image of a vertex from $P_M$ equals an integer $ c $。我们表明，{\ sc加权路径仿真}以$ c $作为参数，对于{\ bf n} $中的所有$ t \而言，对于$ w [t] $来说都是困难的，并且强烈np complete。我们还表明，对于{\ bf n} $中的所有$ t \ $ w [t] $的定向带宽，对于有向的无环形图，其基本的无向图是caterpillar。
In this paper, we show that Bandwidth is hard for the complexity class $W[t]$ for all $t\in {\bf N}$, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path $P_N$ and integer $M$, decide if there exists a mapping of the vertices of $P_N$ to a path $P_M$, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the image of a vertex from $P_M$ equals an integer $c$. We show that {\sc Weighted Path Emulation}, with $c$ as parameter, is hard for $W[t]$ for all $t\in {\bf N}$, and is strongly NP-complete. We also show that Directed Bandwidth is hard for $W[t]$ for all $t\in {\bf N}$, for directed acyclic graphs whose underlying undirected graph is a caterpillar.
