Source author record

Vaishali Surianarayanan

Vaishali Surianarayanan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Databases Social and Information Networks

Catalog footprint

What is connected

2works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Counting hypertriangles through hypergraph orientations

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 hypergraphs, motivating the need for efficient hypergraph motif counting algorithms. In particular, we study the problem of counting hypertriangles - collections of three pairwise-intersecting hyperedges. These hypergraph patterns have a rich structure with multiple distinct intersection patterns unlike graph triangles. Inspired by classical graph algorithms based on orientations and degeneracy, we develop a theoretical framework that generalizes these concepts to hypergraphs and yields provable algorithms for hypertriangle counting. We implement these ideas in DITCH (Degeneracy Inspired Triangle Counter for Hypergraphs) and show experimentally that it is 10-100x faster and more memory efficient than existing state-of-the-art methods.

preprint2020arXiv

A Parameterized Approximation Scheme for Min $k$-Cut

In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than $2$. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al.~[SODA 2018] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave an $1.9997$-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors~[FOCS 2018] designed an $(1 +ε)$-approximation algorithm that runs in time $(k/ε)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$, and a $1.81$-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin~[SODA 2020] gave a $(5/3 + ε)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every $ε> 0$, the algorithm obtains a $(1 +ε)$-approximate solution in time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest.