Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
复制标题
一些图基序问题的参数化算法和硬度结果
DOI：
10.1007/978-3-540-69068-9_6
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
Nadja Betzler;M. Fellows;Christian Komusiewicz;R. Niedermeier
我们研究了NP完整的图基序：给定顶点颜色的图G =（V，E）和多式MOF颜色，是否存在si¾？多重性）M中的颜色？我们提出了一个改进的随机算法，用于运行时间o（4.32 | M |·| M | 2·| e |）。在哪里主题G [S]不需要通过对比来连接。我们表明，发现（未颜色）双连接或与桥相连的子图的简单问题是关于子图大小的w [1] - 整理。证明参数“连接的基序成分的数量”也会导致w [1] - hards，即使仅限于路径的图形。
We study the NP-complete Graph Motif problem: given a vertex-colored graph G= (V,E) and a multiset Mof colors, does there exist an Si¾? Vsuch that G[S] is connected and carries exactly (also with respect to multiplicity) the colors in M? We present an improved randomized algorithm for Graph Motif with running time O(4.32|M|·|M|2·|E|). We extend our algorithm to list-colored graph vertices and the case where the motif G[S] needs not be connected. By way of contrast, we show that extending the request for motif connectedness to the somewhat "more robust" motif demands of biconnectedness or bridge-connectedness leads to W[1]-complete problems. Actually, we show that the presumably simpler problems of finding (uncolored) biconnected or bridge-connected subgraphs are W[1]-complete with respect to the subgraph size. Answering an open question from the literature, we further show that the parameter "number of connected motif components" leads to W[1]-hardness even when restricted to graphs that are paths.