Engineering Motif Search for Large Graphs
(2015) ALENEX In [Host publication title missing] p.104118 Abstract
 In the graph motif problem, we are given as input a vertexcolored 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 NPcomplete 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 topologyinvariant 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 vertexcolored 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 NPcomplete 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 topologyinvariant 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:
http://lup.lub.lu.se/record/4905375
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri; Kowalik, Lukasz and Lauri, Juho
 organization
 publishing date
 2015
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 [Host publication title missing]
 editor
 Brandes, Ulrik; Eppstein, David; and
 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
 048918d97f294f94b9f70b03b789b289 (old id 4905375)
 date added to LUP
 20150107 11:18:27
 date last changed
 20180529 10:04:15
@inproceedings{048918d97f294f94b9f70b03b789b289, abstract = {In the graph motif problem, we are given as input a vertexcolored 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 NPcomplete 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 topologyinvariant 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 = {104118}, title = {Engineering Motif Search for Large Graphs}, url = {http://dx.doi.org/10.1137/1.9781611973754.10}, year = {2015}, }