215 citations · 318 across the 83 of their papers we have counts for
11 papers · 1 filter
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak +1
We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, inclu…
Sublinear Algorithms for -Approximate Matching
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime…
Deterministic Small Vertex Connectivity in Almost Linear Time
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
In the vertex connectivity problem, given an undirected -vertex -edge graph , we need to compute the minimum number of vertices that can disconnect after removing them…
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g.,…
Vertex Sparsifiers for Hyperedge Connectivity
Han Jiang, Shang-En Huang, Thatchaphol Saranurak +1
Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for -edge connectivity, which has found applications in parameterized algorith…
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert
Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic grap…
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak +1
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximatio…
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai +3
In the -edge-connected spanning subgraph (ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to link failures: Given an -nod…
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
Yaowei Long, Thatchaphol Saranurak
We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-un…
Near-Linear Time Approximations for Cut Problems via Fair Cuts
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +1
We introduce the notion of {\em fair cuts} as an approach to leverage approximate -mincut (equivalently -maxflow) algorithms in undirected graphs to obtain near-linea…
Space Complexity of Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
A -vertex connectivity oracle for undirected is a data structure that, given , reports , where is the pairwise vertex connectivity be…