Constrained Multilinear Detection and Generalized Graph Motifs
(2016) In Algorithmica 74(2). p.947967 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^∗(2^k)time polynomial space algorithm for the ksized 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, MinSubstitute Graph Motif, and MinAdd Graph Motif. Finally, we provide a piece of evidence that our result might be... (More)
 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^∗(2^k)time polynomial space algorithm for the ksized 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, MinSubstitute Graph Motif, and MinAdd Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an O^∗((2−ϵ)^k)time algorithm for the Graph Motif problem implies an O((2−ϵ′)^n)time algorithm for Set Cover. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/5152001
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Kowalik, Lukasz
 organization
 publishing date
 2016
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Algorithmica
 volume
 74
 issue
 2
 pages
 947  967
 publisher
 Springer
 external identifiers

 wos:000369011300015
 scopus:84955628212
 ISSN
 01784617
 DOI
 10.1007/s0045301599811
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 c0c7cc4ea1f540f4b7e453686f802f47 (old id 5152001)
 date added to LUP
 20150309 14:04:29
 date last changed
 20180218 03:23:26
@article{c0c7cc4ea1f540f4b7e453686f802f47, 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^∗(2^k)time polynomial space algorithm for the ksized 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, MinSubstitute Graph Motif, and MinAdd Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an O^∗((2−ϵ)^k)time algorithm for the Graph Motif problem implies an O((2−ϵ′)^n)time algorithm for Set Cover.}, author = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}, issn = {01784617}, language = {eng}, number = {2}, pages = {947967}, publisher = {Springer}, series = {Algorithmica}, title = {Constrained Multilinear Detection and Generalized Graph Motifs}, url = {http://dx.doi.org/10.1007/s0045301599811}, volume = {74}, year = {2016}, }