38 citations · 53 across the 13 of their papers we have counts for
17 papers · 1 filter
A Simple Subquadratic Cut Query Protocol for Directed Reachability
Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
We study -- reachability in an unweighted directed graph on vertices, accessed through a directed cut oracle: given , the oracle returns the number of edges…
Bipartite Matching with Few Rounds of Demand Queries
Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisa…
The Power of the Score Sequence of a Tournament
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra +1
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs…
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1
Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed varian…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay +1
We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweigh…
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff +2
The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang, Sagnik Mukhopadhyay
We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer , our algorithm can, with high probability…
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai +1
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" al…
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Joakim Blikstad, Jan van den Brand, Yuval Efron +2
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AN…
Cut query algorithms with star contraction
Simon Apers, Yuval Efron, Paweł Gawrychowski +3
We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge c…
A Note on Isolating Cut Lemma for Submodular Function Minimization
Sagnik Mukhopadhyay, Danupon Nanongkai
It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the…
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For for any constant , our algorit…
Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay +1
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $\…
Faster connectivity in low-rank hypergraphs via expander decomposition
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay +1
We design an algorithm for computing connectivity in hypergraphs which runs in time (the hides th…
Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay +1
Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], ther…
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
Consider the following 2-respecting min-cut problem. Given a weighted graph and its spanning tree , find the minimum cut among the cuts that contain at most two edges in …