5 papers · 1 filter
Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
Akash Kumar, Abhiruk Lahiri, C. Seshadhri
Consider a bounded-degree graph that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $…
Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
Daniel Paul-Pena, C. Seshadhri
Counting small patterns in a large dataset is a fundamental algorithmic task. The most common version of this task is subgraph/homomorphism counting, wherein we count the number of…
Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
Daniel Paul-Pena, C. Seshadhri
We study the classic problem of subgraph counting, where we wish to determine the number of occurrences of a fixed pattern graph in an input graph of vertices. Our focu…
Improved Massively Parallel Triangle Counting in Rounds
Quanquan C. Liu, C. Seshadhri
In this short note, we give a novel algorithm for round triangle counting in bounded arboricity graphs. Counting triangles in rounds (exactly) is listed as one of the…
A Dichotomy Hierarchy Characterizing Linear Time Subgraph Counting in Bounded Degeneracy Graphs
Daniel Paul-Pena, C. Seshadhri
Subgraph and homomorphism counting are fundamental algorithmic problems. Given a constant-sized pattern graph and a large input graph , we wish to count the number of -ho…