- Title
- Parameterized algorithms and hardness results for some graph Motif problems
- Creator
- Betzler, Nadja; Fellows, Michael R.; Komusiewicz, Christian; Niedermeier, Rolf
- Relation
- 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008). Combinatorial Pattern Matching (Pisa, Italy 18-20 June, 2008) p. 31-43
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-69068-9_6
- Publisher
- Springer Berlin
- Resource Type
- conference paper
- Date
- 2008
- Description
- We study the NP-complete Graph Motif problem: given a vertex-colored graph G = (V,E) and a multiset M of colors, does there exist an S ⊆ V such 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|²‧|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.
- Subject
- Graph Motif problem; graphs; randomized algorithms; vertices; bridge-connectedness
- Identifier
- http://hdl.handle.net/1959.13/45029
- Identifier
- uon:5973
- Identifier
- ISBN:9783540690665
- Language
- eng
- Reviewed
- Hits: 874
- Visitors: 1036
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|