Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/45029
- Title
- Parameterized algorithms and hardness results for some graph Motif problems
- Author/Creator
-
Betzler, Nadja;
Fellows, Michael R.;
Komusiewicz, Christian;
Niedermeier, Rolf
- Institution
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- 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.
- 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
- Date
- 2008
- Publisher
- Springer Berlin
- Keyword(s)
-
Graph Motif problem;
graphs;
randomized algorithms;
vertices;
bridge-connectedness
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/45029
- Identifier
- ISBN:9783540690665
- Reviewed
19 Visitors
20 Hits
0 Downloads
