Constrained multilinear detection and generalized graph motifs

DOI10.1007/S00453-015-9981-1zbMATH Open1336.68115DBLPjournals/algorithmica/BjorklundKK16arXiv1209.1082OpenAlexW2073438136WikidataQ59473175 ScholiaQ59473175MaRDI QIDQ262282FDOQ262282

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

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

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^{*}(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.

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

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

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)

Cites Work

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

Cited In (21)

• Title not available (Why is that?)
• 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
• The maximum binary tree problem
• Constrained multilinear detection for faster functional motif discovery
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Parameterized pre-coloring extension and list coloring problems
• Title not available (Why is that?)
• 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
• On the Complexity of Bounded Context Switching.
• Parameterized algorithms for list \(K\)-cycle
• 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)