Advanced

Engineering Motif Search for Large Graphs

Björklund, Andreas LU ; Kaski, Petteri; Kowalik, Lukasz and Lauri, Juho (2015) ALENEX In [Host publication title missing] p.104-118
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
[Host publication title missing]
editor
Brandes, Ulrik and Eppstein, David
pages
15 pages
conference name
ALENEX
external identifiers
  • Scopus:84937777832
DOI
10.1137/1.9781611973754.10
project
Exact algorithms
language
English
LU publication?
yes
id
048918d9-7f29-4f94-b9f7-0b03b789b289 (old id 4905375)
date added to LUP
2015-01-07 11:18:27
date last changed
2016-10-13 04:59:06
@misc{048918d9-7f29-4f94-b9f7-0b03b789b289,
  abstract     = {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.},
  author       = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz and Lauri, Juho},
  editor       = {Brandes, Ulrik and Eppstein, David},
  language     = {eng},
  pages        = {104--118},
  series       = {[Host publication title missing]},
  title        = {Engineering Motif Search for Large Graphs},
  url          = {http://dx.doi.org/10.1137/1.9781611973754.10},
  year         = {2015},
}