6 papers
Counting hypertriangles through hypergraph orientations
Daniel Paul-Pena, Vaishali Surianarayanan, Deeparnab Chakrabarty +1
Counting the number of small patterns is a central task in network analysis. While this problem is well studied for graphs, many real-world datasets are naturally modeled as hyperg…
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…
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…
A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
Daniel Paul-Pena, C. Seshadhri
Counting the number of homomorphisms of a pattern graph H in a large input graph G is a fundamental problem in computer science. There are myriad applications of this problem in da…