Constrained Multilinear Detection and Generalized Graph Motifs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
21
Series
Algorithmica, Volume 74, issue 2, pp. 947-967
Abstract
We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed to have coefficients from a field of characteristic two. As applications of the technique, we show an O∗(2k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute Graph Motif, and Min-Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an (Formula Presented.)-time algorithm for the Graph Motif problem implies an (Formula Presented.)-time algorithm for Set Cover.Description
Other note
Citation
Björklund, A, Kaski, P & Kowalik, Ł 2016, 'Constrained Multilinear Detection and Generalized Graph Motifs', Algorithmica, vol. 74, no. 2, pp. 947-967. https://doi.org/10.1007/s00453-015-9981-1