3 papers
cs.DS2026
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 $…
cs.DS2025
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…
cs.DS2025
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…