Faster algorithms for finding and counting subgraphs

DOI10.1016/j.jcss.2011.10.001zbMath1246.05149WikidataQ60488486 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

treewidth; counting; homomorphism; subgraph isomorphism; parameterized complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C30: Enumeration in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

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