Name
Abstract | ||
|---|---|---|
We study the NP-complete Graph Motifproblem: given a vertex-colored graph G= (V,E) and a multiset Mof colors, does there exist an S茂戮驴 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 Motifwith 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69068-9_6 | CPM |
Keywords | Field | DocType |
vertex-colored graph,motif demand,complete problem,motif connectedness,graph motifwith,improved randomized algorithm,connected motif component,list-colored graph vertex,np-complete graph motifproblem,graph motif problems,motif g,parameterized algorithms,hardness results,randomized algorithm,list coloring,complete graph | Discrete mathematics,Combinatorics,Line graph,Graph power,Biconnected graph,Graph factorization,Distance-hereditary graph,Null graph,Factor-critical graph,Mathematics,Complement graph | Conference |
Volume | ISSN | Citations |
5029 | 0302-9743 | 24 |
PageRank | References | Authors |
1.04 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nadja Betzler | 1 | 501 | 24.69 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Christian Komusiewicz | 3 | 461 | 46.04 |
| Rolf Niedermeier | 4 | 3465 | 234.21 |