Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Engineering Motif Search for Large Graphs

Björklund, Andreas LU ; Kaski, Petteri ; Kowalik, Lukasz and Lauri, Juho (2015) ALENEX 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
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
[Host publication title missing]
editor
Brandes, Ulrik and Eppstein, David
pages
15 pages
conference name
ALENEX
conference dates
2015-01-05
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
2016-04-04 13:59:50
date last changed
2022-04-08 18:42:08
@inproceedings{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}},
  booktitle    = {{[Host publication title missing]}},
  editor       = {{Brandes, Ulrik and Eppstein, David}},
  language     = {{eng}},
  pages        = {{104--118}},
  title        = {{Engineering Motif Search for Large Graphs}},
  url          = {{http://dx.doi.org/10.1137/1.9781611973754.10}},
  doi          = {{10.1137/1.9781611973754.10}},
  year         = {{2015}},
}