Tampere University of Technology

TUTCRIS Research Portal

Engineering motif search for large graphs

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Details

Original languageEnglish
Title of host publication2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)
Pages104-118
Number of pages15
ISBN (Electronic)978-1-61197-375-4
DOIs
Publication statusPublished - 2015
Publication typeA4 Article in a conference publication
EventWorkshop on Algorithm Engineering and Experiments -
Duration: 1 Jan 1900 → …

Publication series

NameWorkshop on Algorithm Engineering and Experiments
ISSN (Print)2164-0300

Conference

ConferenceWorkshop on Algorithm Engineering and Experiments
Abbreviated titleALENEX
Period1/01/00 → …

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 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 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.

ASJC Scopus subject areas

Publication forum classification

Field of science, Statistics Finland