7 papers
Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts
Sabyasachi Basu, C. Seshadhri
Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meanin…
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…
Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
Sabyasachi Basu, Daniel Paul-Pena, Kun Qian +3
Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of…
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…