Faster algorithms for finding and counting subgraphs

DOI10.1016/j.jcss.2011.10.001zbMath1246.05149OpenAlexW2089369802WikidataQ60488486 ScholiaQ60488486MaRDI QIDQ439930

Venkatesh Raman, Daniel Lokshtanov, Saket Saurabh, Fedor V. Fomin, B. V. Raghavendra Rao

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.001

zbMATH Keywords

treewidthcountinghomomorphismsubgraph isomorphismparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Randomized parameterized algorithms for the kidney exchange problem, Exact Weight Subgraphs and the k-Sum Conjecture, Improved Parameterized Algorithms for Network Query Problems, Improved parameterized algorithms for network query problems, Sublinear-time algorithms for counting star subgraphs via edge sampling, Clearing directed subgraphs by mobile agents. Variations on covering with paths, Fixed-parameter tractability of satisfying beyond the number of variables, Detecting and Counting Small Pattern Graphs, Algebraic methods in the congested clique, Unnamed Item, Unnamed Item, Unnamed Item, Stable matching games: manipulation via subgraph isomorphism, Counting Answers to Existential Questions, A Slice Theoretic Approach for Embedding Problems on Digraphs, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• The vertex separation number of a graph equals its path-width
• Treewidth. Computations and approximations
• Counting \(H-\)colorings of partial \(k-\)trees
• Trimmed Moebius inversion and graphs of bounded degree
• Narrow sieves for parameterized paths and packings
• Balanced families of perfect hash functions and their applications
• Faster Algebraic Algorithms for Path and Packing Problems
• Divide-and-Color
• Limits and Applications of Group Algebras for Parameterized Problems
• Counting Paths and Packings in Halves
• Computational aspects of the Mobius transformation of graphs
• Color-coding
• The Parameterized Complexity of Counting Problems
• Finding, minimizing, and counting weighted subgraphs
• Counting Subgraphs via Homomorphisms