Constrained multilinear detection and generalized graph motifs

DOI10.1007/S00453-015-9981-1MaRDI QIDQ262282zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andreas Björklund, Petteri Kaski, Łukasz Kowalik

Publication date 29 March 2016

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1209.1082

zbMATH Keywords

constrained multilinear detectionFPT algorithmgraph motif

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Polynomials over finite fields (11T06)

Abstract: We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. As applications of the technique, we show an $O^{\ast }(2^k)$-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 $O^{\ast }((2-epsilon{)}^k)$-time algorithm for the Graph Motif problem implies an $O((2-epsilo{n}^{\prime }{)}^n)$-time algorithm for Set Cover.

Recommendations

• Constrained multilinear detection for faster functional motif discovery
• Probably optimal graph motifs
• Engineering motif search for large motifs
• Engineering Motif Search for Large Graphs
• Deterministic parameterized algorithms for the graph motif problem

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• A probabilistic remark on algebraic program testing
• Constrained multilinear detection for faster functional motif discovery
• Counting perfect matchings as fast as Ryser
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding and counting vertex-colored subtrees
• Finding approximate and constrained motifs in graphs
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Limits and Applications of Group Algebras for Parameterized Problems
• Maximum Motif Problem in Vertex-Colored Graphs
• Narrow sieves for parameterized paths and packings
• On problems as hard as CNF-SAT
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Probably optimal graph motifs
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

Cited in

(21)

• scientific article; zbMATH DE number 7559154 (Why is no real title available?)
• On the maximum colorful arborescence problem and color hierarchy graph structure
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Fine-grained complexity of safety verification
• Constrained multilinear detection for faster functional motif discovery
• The maximum binary tree problem
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Parameterized pre-coloring extension and list coloring problems
• scientific article; zbMATH DE number 7561312 (Why is no real title available?)
• Quasipolynomial representation of transversal matroids with applications in parameterized complexity
• Narrow sieves for parameterized paths and packings
• Graph motif problems parameterized by dual
• Probably optimal graph motifs
• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Engineering motif search for large motifs
• Univariate ideal membership parameterized by rank, degree, and number of generators
• Parameterized algorithms for list \(K\)-cycle
• On the Complexity of Bounded Context Switching.
• The graph motif problem parameterized by the structure of the input graph
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Exact exponential algorithms to find tropical connected sets of minimum size

This page was built for publication: Constrained multilinear detection and generalized graph motifs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262282)