Paul Pena, D. (CSE) – Efficient Pattern Counting in Sparse Graphs and Hypergraphs

Pattern counting is a fundamental problem in computer science with applications in many domains. For a fixed small pattern H, we are given a large graph G and we are asked to count the number of subgraphs or homomorphisms (edge-preserving maps) of H in G. For practical applications where the input graph can be very large, we are interested in finding efficient algorithms, that is, algorithms that run in linear or subquadratic time with respect to the size of the input.

Finding such algorithms in general (when G can be any graph) is not possible. Instead, we restrict our input to sparse classes of graphs. One family of graph classes that has been widely studied in the context of subgraph and homomorphism counting is bounded-degeneracy graph classes. Real-world graphs in many domains have bounded degeneracy, so studying these classes in theory can lead to practical algorithms.

A series of advances in the study of homomorphism counting led to a dichotomy theorem that exactly characterized which patterns were linear-time computable for bounded-degeneracy inputs. This dissertation builds on this result, extending it to other variants of this problem, and generalizing it to other different settings, like counting hypergraphs and notions of sparsity beyond degeneracy.

Our results help develop the theory of subgraph counting in sparse graphs and hypergraphs, and showcase how sparsity can be used both in theory and practice to develop faster algorithms.

Event Host: Daniel Paul Pena, Ph.D. Candidate, Computer Science & Engineering 

Advisor: C. Sheshadhri

Zoom: https://ucsc.zoom.us/j/97685906168?pwd=O35brsWilyn2m8AgMn0dKgALBe6wi1.1