论文标题
连接路径的线性固定参数可拖动算法
A linear fixed parameter tractable algorithm for connected pathwidth
论文作者
论文摘要
路径的图参数可以看作是图形与路径的拓扑相似性的度量。在节点搜索方面给出了一个流行的路径宽定义，在该搜索中给出了一种隧道系统，该系统受到某种传染性物质污染的隧道系统，我们正在寻找一种搜索策略，在每个步骤中，要么将搜索器放在顶点上，要么将搜索器从顶点删除搜索器，在两个端点都同时被搜索时，搜索者都会清洁边缘。事实证明，成功清洁策略所需的最小搜索者数量等于图的路径宽度加一个。清洁策略的两个理想特征是单调的（不发生重新污染）并连接（干净的领土始终保持连接）。在这两个要求下，搜索者的数量等效于{\ em em connected路径}的路径宽度的变体。我们证明连接的路径是固定的参数可行的，特别是我们设计了$ 2^{o（k^2）} \ cdot n $ time算法，该算法检查了$ g $的连接路径是否最多是$k。$ $ $k。$ $ $ this consolly this Resol this of [dereniowski，osula，osula and rz smill and rz} ews ews}多项式时间中的路径分解。理论。计算。 Sci。，794：85-100，2019]。对于我们的算法，我们丰富了能够处理连接需求的典型序列技术。典型的序列已在[Bodlaender和Kloks中引入。图形的路径宽和树宽的高效和建设性算法。 J.算法，21（2）：358-402，1996]，用于设计树宽和路径宽度的线性参数化算法。所提出的扩展名是基于连接性属性的编码，该连接性属性具有广泛的功能，并且可以对其他宽度参数的连接变体提供线性参数化算法。
The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rz{ą}{ż}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well.
