Engineering Motif Search for Large Graphs
Author
Editor
- Ulrik Brandes
- David Eppstein
Summary, in English
In the graph motif problem, we are given as input a vertex-colored graph H (the host graph) and a multiset of colors M (the motif). Our task is to decide whether H has a connected set of vertices whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit parameterized algorithms that run in linear time in the size of H. We demonstrate that algorithms based on constrained multilinear sieving are viable in practice, scaling to graphs with hundreds of millions of edges as long as M remains small. Furthermore, our implementation is topology-invariant relative to the host graph H, meaning only the most crude graph parameters (number of edges and number of vertices) suffice in practice to determine the algorithm performance.
Department/s
Publishing year
2015
Language
English
Pages
104-118
Publication/Series
[Host publication title missing]
Document type
Conference paper
Topic
- Computer Science
Conference name
ALENEX
Conference date
2015-01-05
Status
Published
Project
- Exact algorithms