Counting Subgraphs in Degenerate Graphs

DOI10.1145/3520240MaRDI QIDQ5889797zbMATH OpenOpenAlexFDO

Authors Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira

Publication date 27 April 2023

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

degeneracygraph algorithmslinear time algorithmssubgraph counting

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Faster Subgraph Counting in Sparse Graphs
• Faster algorithms for counting subgraphs in sparse graphs
• Homomorphisms are a good basis for counting small subgraphs
• Approximately counting embeddings into random graphs
• Study on the counting of subgraphs in degenerate graph

Cites work

• A course in combinatorics.
• Arboricity and Subgraph Listing Algorithms
• Color-coding
• Counting and detecting small subgraphs via equations
• Counting Paths and Packings in Halves
• Efficient algorithms for clique problems
• Emergence of Scaling in Random Networks
• Faster algorithms for counting subgraphs in sparse graphs
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Finding and counting small induced subgraphs efficiently
• Finding, minimizing, and counting weighted subgraphs
• Generalized quasirandom graphs
• Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• scientific article; zbMATH DE number 2110413 (Why is no real title available?)
• scientific article; zbMATH DE number 7650386 (Why is no real title available?)
• Large networks and graph limits
• Multiplying matrices faster than coppersmith-winograd
• On the complexity of fixed parameter clique and dominating set
• On the Desirability of Acyclic Database Schemes
• Quasi-random graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Sparsity. Graphs, structures, and algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of counting homomorphisms seen from the other side
• The Parameterized Complexity of Counting Problems

Cited in

(17)

• Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
• Supersaturation for subgraph counts
• Counting subgraphs in hyperbolic graphs with symmetry
• scientific article; zbMATH DE number 6322906 (Why is no real title available?)
• Counting Subgraphs via Homomorphisms
• Counting Homomorphic Cycles in Degenerate Graphs
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Parameterised and fine-grained subgraph counting, modulo 2
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting subgraphs in somewhere dense graphs
• Finding and counting small tournaments in large tournaments
• Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
• A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs
• Cycle counting under local differential privacy for degeneracy-bounded graphs
• Partition constraints for conjunctive queries: bounds and worst-case optimal joins
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism
• Parameterised holant problems

This page was built for publication: Counting Subgraphs in Degenerate Graphs

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