Danupon Nanongkai

STOC Conference 2023 Conference Paper

Fast Algorithms via Dynamic-Oracle Matroids

• Joakim Blikstad
• Sagnik Mukhopadhyay
• Danupon Nanongkai
• Ta-Wei Tu

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” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õ k ( n + r √ r ) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õ k hides poly ( k , log( n )). This implies the following consequences. (i) An improvement over the Õ k ( n √ r ) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS’19] for matroid union in the traditional rank-query model. (ii) An Õ k (| E |+| V |√| V |)-time algorithm for the k -disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õ k (| V |√| E |) bounds of Gabow-Westermann [STOC’88] and Gabow [STOC’91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with Õ( n √ r ) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP’85], graphic matroid intersection [Gabow-Xu FOCS’89], simple job scheduling matroid intersection [Xu-Gabow ISAAC’94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a “unified” algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. Lower bounds. We show simple super-linear (Ω( n log n )) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log 2 (3) n − o ( n ) bound by Harvey [SODA’08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS’19].

SODA Conference 2023 Conference Paper

Fully Dynamic Exact Edge Connectivity in Sublinear Time

• Gramoz Goranci
• Monika Henzinger
• Danupon Nanongkai
• Thatchaphol Saranurak
• Mikkel Thorup
• Christian Wulff-Nilsen

Given a simple n -vertex, m -edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ( n ) worst-case update time and Õ( m 1-1/16 ) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].

SODA Conference 2023 Conference Paper

Near-Linear Time Approximations for Cut Problems via Fair Cuts

• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak

We introduce the notion of fair cuts as an approach to leverage approximate ( s, t )-mincut (equivalently ( s, t )-maxflow) algorithms in undirected graphs to obtain near-linear time approximation algorithms for several cut problems. Informally, for any α ≥ 1, an α-fair ( s, t )-cut is an ( s, t )-cut such that there exists an ( s, t )-flow that uses 1/α fraction of the capacity of every edge in the cut. (So, any α-fair cut is also an α-approximate mincut, but not vice-versa.) We give an algorithm for (1 + ε)-fair ( s, t )-cut in Õ ( m )-time, thereby matching the best runtime for (1 + ε)-approximate ( s, t )-mincut [Peng, SODA '16]. We then demonstrate the power of this approach by showing that this result almost immediately leads to several applications: • the first nearly-linear time (1 + ε)-approximation algorithm that computes all-pairs maxflow values (by constructing an approximate Gomory-Hu tree). Prior to our work, such a result was not known even for the special case of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC '03]; • the first almost-linear-work subpolynomial-depth parallel algorithms for computing (1+ε)-approximations for all-pairs maxflow values (again via an approximate Gomory-Hu tree) in unweighted graphs; • the first near-linear time expander decomposition algorithm that works even when the expansion parameter is polynomially small; this subsumes previous incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS '17; Saranurak and Wang, SODA '19]. * The full version of the paper can be accessed at https: //arxiv. org/abs/2203. 00751

FOCS Conference 2022 Conference Paper

Cut Query Algorithms with Star Contraction

• Simon Apers
• Yuval Efron
• Pawel Gawrychowski
• Troy Lee
• Sagnik Mukhopadhyay
• Danupon Nanongkai

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 connectivity with $O(n)$ cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with $\tilde{O}(\sqrt{}$n) cut queries. To prove these results we introduce a new technique, called star contraction, to randomly contract edges of a graph while preserving non-trivial minimum cuts. In star contraction vertices randomly contract an edge incident on a small set of randomly chosen “center” vertices. In contrast to the related 2-out contraction technique of Ghaffari, Nowicki, and Thorup [SODA’20], star contraction only contracts vertex-disjoint star subgraphs, which allows it to be efficiently implemented via cut queries. The $O(n)$ bound from item (i) was not known even for the simpler problem of connectivity, and it improves the $O(n\log^{3}n)$ upper bound by Rubinstein, Schramm, and Weinberg [ITCS’18]. The bound is tight under the reasonable conjecture that the randomized communication complexity of connectivity is $\Omega(n\log n)$, an open question since the seminal work of Babai, Frankl, and Simon [FOCS’86]. The bound also excludes using edge connectivity on simple graphs to prove a superlinear randomized query lower bound for minimizing a symmetric submodular function. The quantum algorithm from item (ii) gives a nearlyquadratic separation with the randomized complexity, and addresses an open question of Lee, Santha, and Zhang [SODA’21]. The algorithm can alternatively be viewed as computing the edge connectivity of a simple graph with $\tilde{O}(\sqrt{}$n) matrix-vector multiplication queries to its adjacency matrix. Finally, we demonstrate the use of star contraction outside of the cut query setting by designing a one-pass semi-streaming algorithm for computing edge connectivity in the complete vertex arrival setting. This contrasts with the edge arrival setting where two passes are required.

FOCS Conference 2022 Conference Paper

Nearly Optimal Communication and Query Complexity of Bipartite Matching

• Joakim Blikstad
• Jan van den Brand
• Yuval Efron
• Sagnik Mukhopadhyay
• Danupon Nanongkai

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to polylogarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC’88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS’12; Dobzinski, Nisan, and Oren STOC’14; Nisan SODA’21] and tighten the lower bounds shown by Beniamini and Nisan [STOC’21] and Zhang [ICALP’04]. We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]). Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.

FOCS Conference 2022 Conference Paper

Negative-Weight Single-Source Shortest Paths in Near-linear Time

• Aaron Bernstein
• Danupon Nanongkai
• Christian Wulff-Nilsen

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O\left(m \log ^{8}(n) \log W\right)$ time when edge weights are integral and can be negative. 1 This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde{O}\left(\left(m+n^{1. 5}\right) \log W\right)$ [BLNPSSSW FOCS’20] and $m^{4 / 3+o(1)} \log W$ [AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $O(m \sqrt{n} \log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP’89].

STOC Conference 2021 Conference Paper

Breaking the quadratic barrier for matroid intersection

• Joakim Blikstad
• Jan van den Brand
• Sagnik Mukhopadhyay
• Danupon Nanongkai

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 M 1 = ( V , I 1 ) and M 2 = ( V , I 2 ) on a comment ground set V of n elements, and then we have to find the largest common independent set S ∈ I 1 ∩ I 2 by making independence oracle queries of the form ”Is S ∈ I 1 ?” or ”Is S ∈ I 2 ?” for S ⊆ V . The goal is to minimize the number of queries. Beating the existing Õ( n 2 ) bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunningham’s algorithm [SICOMP 1986], whose Õ( n 2 )-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019] (more generally, these algorithms take Õ( nr ) queries where r denotes the rank which can be as big as n ). The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with o ( n 2 ) independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing Õ( n 9/5 ) independence queries with high probability, and a deterministic algorithm guaranteeing Õ( n 11/6 ) independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results.

STOC Conference 2021 Conference Paper

Distributed weighted min-cut in nearly-optimal time

• Michal Dory
• Yuval Efron
• Sagnik Mukhopadhyay
• Danupon Nanongkai

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], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]) can guarantee a solution that is (1+є)-approximation at best while the exact Õ( n 0.8 D 0.2 + n 0.9 )-time algorithm [Ghaffari, Nowicki, Thorup, SODA’20] works only on simple networks (no weights and no parallel edges). Throughout, n and D denote the network’s number of vertices and hop-diameter, respectively. For the weighted case, the best bound was Õ( n ) [Daga, Henzinger, Nanongkai, Saranurak, STOC’19]. In this paper, we provide an exact Õ(√ n + D )-time algorithm for computing min-cut on weighted networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC’20] and can be of independent interest.

SODA Conference 2021 Conference Paper

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time

• Sayan Bhattacharya
• Monika Henzinger
• Danupon Nanongkai
• Xiaowei Wu 0001

In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal min( O (log n ), f ) approximation factor. (Throughout, m, n, f, and C are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when f = Ω(log n ), this was achieved by a deterministic O (log n )-approximation algorithm with O ( f log n ) amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic (1 + ∊) f -approximation algorithm with O ( f log( Cn )/ ∊ 2 ) amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: (1) (1 + ∊) f -approximation ratio in O ( f log 2 ( Cn )/∊ 3 ) worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the O (log 3 n/ poly(∊)) worst-case update time for unweighted dynamic vertex cover (i. e. , when f = 2 and C = 1) by Bhattacharya et al. [SODA'17]. (2) (1 + ∊) f - approximation ratio in O (( f 2 / ∊ 3 ) + ( f/∊ 2 ) log C ) amortized update time: This result improves the previous O ( f log ( Cn )/ ∊ 2 ) update time bound for most values of f in the low-frequency range, i. e. whenever f = o (log n ). It is the first that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i. e. , when f = 2 and C = 1). These results are achieved by leveraging the approximate complementary slackness and background schedulers techniques. These techniques were used in the local update scheme for dynamic vertex cover. Our main technical contribution is to adapt these techniques within the global update scheme of Bhattacharya et al. [FOCS'19] for the dynamic set cover problem.

FOCS Conference 2021 Conference Paper

Minimum Cuts in Directed Graphs via Partial Sparsification

• Ruoxu Cen
• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Kent Quanrud

We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde{O}(n\cdot\max\{m^{2/3}, \ n\})$ time. This improves on the 30 year old bound of $\tilde{O}(nm)$ obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain $\tilde{O}(n^{2}/\epsilon^{2})$ -time $(1+{\epsilon})$ -approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed $\epsilon$. Before our work, no (1 + $\epsilon)$ -approximation algorithm better than the exact runtime of $\tilde{O}(nm)$ is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to $\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$ calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

STOC Conference 2021 Conference Paper

Vertex connectivity in poly-logarithmic max-flows

• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Sorrachai Yingchareonthawornchai

The vertex connectivity of an m -edge n -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in ( m α ) time for any α ≥ 1, if there is a m α -time maxflow algorithm. Using the current best maxflow algorithm that runs in m 4/3+ o (1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m 4/3+ o (1) -time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ( mn )-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o ( mn ) running time was known before our work, even if we assume an ( m )-time maxflow algorithm. Our new technique is robust enough to also improve the best Õ( mn )-time bound for directed vertex connectivity to mn 1−1/12+ o (1) time

FOCS Conference 2020 Conference Paper

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

• Julia Chuzhoy
• Yu Gao 0001
• Jason Li 0006
• Danupon Nanongkai
• Richard Peng
• Thatchaphol Saranurak

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1 ≤ r ≤ O(logn), computes a (logm) r2 -approximation for Minimum Balanced Cut in G, in time O(m 1+O(1/r)+o(1) ·(logm) O(r2 )). In particular, we obtain a (logm) 1/ε -approximation in time m 1+O(√{ε}) for any constant, and a (logm) f(m) -approximation in time m 1+o(1), for any slowly growing function f(m). We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is n o(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.

FOCS Conference 2020 Conference Paper

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

• Jan van den Brand
• Yin Tat Lee
• Danupon Nanongkai
• Richard Peng
• Thatchaphol Saranurak
• Aaron Sidford
• Zhao Song 0002
• Di Wang 0005

We present an $\tilde{O}(m+n^{1. 5})$ -time randomized algorithm for maximum cardinality bipartite matching and related problems (e. g. transshipment, negative-weight shortest paths, and optimal transport) on m-edge, n-node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i. e. $m=\Omega(n^{1. 5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$ -time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\widetilde{O}(n^{\omega})$ -time algorithms [Ibarra-Moran 1981] (where currently $\omega\approx 2. 373$ ). On sparser graphs, i. e. when $m=n^{9/8+\delta}$ for any constant $\delta > 0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $\widetilde{O}(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v. d. Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v. d. Brand et al. ] and our new IPMs. Combining this general machinery yields a simpler $\widetilde{O}(n\sqrt{m})$ time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art $\widetilde{O}(m+n^{1. 5})$ time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v. d. Brand et al. ]).

SODA Conference 2020 Conference Paper

Coarse-Grained Complexity for Dynamic Algorithms

• Sayan Bhattacharya
• Danupon Nanongkai
• Thatchaphol Saranurak

SODA Conference 2020 Conference Paper

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

• Sebastian Forster
• Danupon Nanongkai
• Liu Yang
• Thatchaphol Saranurak
• Sorrachai Yingchareonthawornchai

Consider the following “local” cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most v edges can be reached from x (a “local” cut) or output ⊥ to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν. In this paper we consider a slack variant of this problem where, when such a cut exists, we can output a cut with up to O ( kν ) edges reachable from x. We present a simple randomized algorithm spending O ( k 2 ν ) time and O ( kν ) queries for the above variant, improving in particular a previous time bound of O ( k O ( k ) ν ) by Chechik et al. [SODA’17]. We also extend our algorithm to handle an approximate variant. We demonstrate that these local algorithms are versatile primitives for designing substantially improved algorithms for classic graph problems by providing the following three applications. (Throughout, Õ ( T ) hides polylog( T ).) A randomized algorithm for the classic k -vertex connectivity problem that takes near-linear time when k = O (polylog( n )), namely Õ ( m + nk 3 ) time in undirected graphs. Prior to our work, the state of the art for this range of k were linear-time algorithms for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73] and a recent algorithm with Õ ( m + n 4/3 k 7/3 ) time [Nanongkai et al. , STOC’19]. The story is the same for directed graphs where our Õ (mk 2 )-time algorithm is near-linear when k = O (polylog( n )). Our techniques also yield an improved approximation scheme. Property testing algorithms for k -edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC’97] and one by Orenstein and Ron [Theor. Comput. Sci. ’11]. A faster algorithm for computing the maximal k- edge connected subgraphs, improving prior work of Chechik et al. [SODA’17].

STOC Conference 2020 Conference Paper

Weighted min-cut: sequential, cut-query, and streaming algorithms

• Sagnik Mukhopadhyay
• Danupon Nanongkai

FOCS Conference 2019 Conference Paper

A New Deterministic Algorithm for Dynamic Set Cover

• Sayan Bhattacharya
• Monika Henzinger
• Danupon Nanongkai

We present a deterministic dynamic algorithm for maintaining a (1+ε)f-approximate minimum cost set cover with O(f log(Cn)/ε^2) amortized update time, when the input set system is undergoing element insertions and deletions. Here, n denotes the number of elements, each element appears in at most f sets, and the cost of each set lies in the range [1/C, 1]. Our result, together with that of Gupta~et~al. ~[STOC'17], implies that there is a deterministic algorithm for this problem with O(f log(Cn)) amortized update time and O(min(log n, f)) -approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only O(log (Cn)) away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was O(f^2), which was due to Bhattacharya~et~al. ~[ICALP`15]. In contrast, the only result that guaranteed O(f) -approximation was obtained very recently by Abboud~et~al. ~[STOC`19], who designed a dynamic algorithm with (1+ε)f-approximation ratio and O(f^2 log n/ε) amortized update time. Besides the extra O(f) factor in the update time compared to our and Gupta~et~al. 's results, the Abboud~et~al. ~algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. This approach was pursued previously by Bhattacharya~et~al. ~and Gupta~et~al. , but not in the recent paper by Abboud~et~al. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed.

STOC Conference 2019 Conference Paper

Breaking quadratic time for small vertex connectivity and an approximation scheme

• Danupon Nanongkai
• Thatchaphol Saranurak
• Sorrachai Yingchareonthawornchai

Vertex connectivity a classic extensively-studied problem. Given an integer k , its goal is to decide if an n -node m -edge graph can be disconnected by removing k vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O ( n 2 ) time even for k =4 and m = O ( n ). In the simplest case where m = O ( n ) and k = O (1), the O ( n 2 ) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For higher m , O ( m ) time is known for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73], the first O ( n 2 ) time is from [Kanevsky, Ramachandran, FOCS’87] for k =4 and from [Nagamochi, Ibaraki, Algorithmica’92] for k = O (1). For general k and m , the best bound is Õ(min( kn 2 , n ω + nk ω )) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86] where Õ hides polylogarithmic terms and ω<2.38 is the matrix multiplication exponent. In this paper, we present a randomized Monte Carlo algorithm with Õ( m + k 7/3 n 4/3 ) time for any k = O (√ n ). This gives the first subquadratic time bound for any 4≤ k ≤ o ( n 2/7 ) (subquadratic time refers to O ( m )+ o ( n 2 ) time.) and improves all above classic bounds for all k ≤ n 0.44 . We also present a new randomized Monte Carlo (1+є)-approximation algorithm that is strictly faster than the previous Henzinger’s 2-approximation algorithm [J. Algorithms’97] and all previous exact algorithms. The story is the same for the directed case, where our exact Õ( min{ km 2/3 n , km 4/3 } )-time for any k = O (√ n ) and (1+є)-approximation algorithms improve classic bounds for small and large k , respectively. Additionally, our algorithm is the first approximation algorithm on directed graphs. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit o ( n 2 ) time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k “near” a given seed node.

STOC Conference 2019 Conference Paper

Distributed edge connectivity in sublinear time

• Mohit Daga
• Monika Henzinger
• Danupon Nanongkai
• Thatchaphol Saranurak

We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ( n 1−1/353 D 1/353 + n 1−1/706 ) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ( n 1−є )) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ= O ( n 1/8−є ) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k -edge connectivity certificate for any k = O ( n 1−є ) in time Õ(√ nk + D ). The previous sublinear-time algorithm can do so only when k = o (√ n ) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω( mk ) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ( n )-time algorithm for computing exact minimum cut for weighted graphs.

STOC Conference 2019 Conference Paper

Distributed exact weighted all-pairs shortest paths in near-linear time

• Aaron Bernstein
• Danupon Nanongkai

In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity ). The problem admits (1+ o (1))-approximation Θ( n )-time algorithm and a nearly-tight Ω( n ) lower bound [Nanongkai, STOC’14; Lenzen and Patt-Shamir PODC’15]. For the exact case, Elkin [STOC’17] presented an O ( n 5/3 log 2/3 n ) time bound, which was later improved to Õ( n 5/4 ) in [Huang, Nanongkai, Saranurak FOCS’17].It was shown that any super-linear lower bound (in n ) requires a new technique [Censor-Hillel, Khoury, Paz, DISC’17], but otherwise it remained widely open whether there exists a Õ( n )-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) Õ( n )-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous Õ( n 5/4 ) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous Õ( n 5/4 ) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ... poly ( n )}). The previously best algorithm for this more difficult setting required Õ( n 3/2 ) time [Agarwal and Ramachandran, ArXiv’18] (this can be improved to Õ( n 4/3 ) if one allows bidirectional communication).

FOCS Conference 2019 Conference Paper

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time

• Jan van den Brand
• Danupon Nanongkai

Consider the following distance query for an n-node graph G undergoing edge insertions and deletions: given two sets of nodes I and J, return the distances between every pair of nodes in I×J. This query is rather general and captures several versions of the dynamic shortest paths problem. In this paper, we develop an efficient (1 + ε)-approximation algorithm for this query using fast matrix multiplication. Our algorithm leads to answers for some open problems for Single-Source and All-Pairs Shortest Paths (SSSP and APSP), as well as for Diameter, Radius, and Eccentricities. Below are some highlights. Note that all our algorithms guarantee worst-case update time and are randomized (Monte Carlo), but do not need the oblivious adversary assumption. Subquadratic update time for SSSP, Diameter, Centralities, ect. : When we want to maintain distances from a single node explicitly (without queries), a fundamental question is to beat trivially calling Dijkstra's static algorithm after each update, taking Θ(n 2 ) update time on dense graphs. A better time complexity was not known even with amortization. It was known to be improbable for exact algorithms and for combinatorial any-approximation algorithms to polynomially beat the Ω(n 2 ) bound (under some conjectures) [Roditty, Zwick, ESA'04; Abboud, V. Williams, FOCS'14]. 1 Our algorithm with I = {s} and J = V (G) implies a (1 + ε)-approximation algorithm for this, guaranteeing Õ(n 1. 823 /ε 2 ) worst-case update time for directed graphs with positive real weights in [1, W]. 2 With ideas from [Roditty, V. Williams, STOC'13], we also obtain the first subquadratic worst-case update time for (5/3 + ε)-approximating the eccentricities and (1. 5 + ε)-approximating the diameter and radius for unweighted graphs (with small additive errors). We also obtain the first subquadratic worst-case update time for (1 + ε)-approximating the closeness centralities for undirected unweighted graphs. Worst-case update time for APSP: When we want to maintain distances between all-pairs of nodes explicitly, the Õ(n 2 ) amortized update time by Demetrescu and Italiano [STOC'03] already matches the trivial Ω(n 2 ) lower bound. A fundamental question is whether it can be made worst-case. The state-of-the-art algorithm takes Õ(n 2+2/3 ) worst-case update time to maintain the distances exactly [Abraham, Chechik, Krinninger, SODA'17; Thorup STOC'05]. When it comes to (1+ε) approximation, this bound is still higher than calling the Õ(n ω /ε)-time static algorithm of Zwick [FOCS'98], where ω ≈ 2. 373. Our algorithm with I = J = V (G) implies nearly tight bounds for this, namely Õ(n 2 /ε 1+ω ) for undirected unweighted graphs and Õ(n 2. 045 /ε 2 ) for directed graphs with positive real weights. Besides this, we also obtain the first dynamic APSP algorithm with subquadratic update time and sublinear query time.

FOCS Conference 2019 Conference Paper

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds

• Jan van den Brand
• Danupon Nanongkai
• Thatchaphol Saranurak

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems whose complexity is not yet well-understood, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachability, distances, maximum matching size, and k-paths/cycles in a graph. Understanding the complexity of dynamic matrix inverse is a key to understand these problems. In this paper, we present (i) improved algorithms for dynamic matrix inverse and their extensions to some incremental/look-ahead variants, and (ii) variants of the Online Matrix-Vector conjecture [Henzinger~et~al. STOC'15] that, if true, imply that these algorithms are tight. Our algorithms automatically lead to faster dynamic algorithms for the aforementioned problems, some of which are also tight under our conjectures, e. g. reachability and maximum matching size (closing the gaps for these two problems was in fact asked by Abboud and V. Williams [FOCS'14]). Prior best bounds for most of these problems date back to more than a decade ago [Sankowski FOCS'04, COCOON'05, SODA'07; Kavitha FSTTCS'08; Mucha and Sankowski Algorithmica'10; Bosek et al. FOCS'14]. Our improvements stem mostly from the ability to use fast matrix multiplication “one more time'', to maintain a certain transformation matrix which could be maintained only combinatorially previously (i. e. without fast matrix multiplication). Oddly, unlike other dynamic problems where this approach, once successful, could be repeated several times (“bootstrapping''), our conjectures imply that this is not the case for dynamic matrix inverse and some related problems. However, when a small additional “look-ahead'' information is provided we can perform such repetition to drive the bounds down further.

FOCS Conference 2018 Conference Paper

A Faster Distributed Single-Source Shortest Paths Algorithm

• Sebastian Forster
• Danupon Nanongkai

We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights in the CONGEST model of distributed computing. While close-to-optimal solutions, in terms of the number of rounds spent by the algorithm, have recently been developed for computing SSSP approximately, the fastest known exact algorithms are still far away from matching the lower bound of Ω (n + D) rounds by Peleg and Rubinovich [SIAM Journal on Computing 2000], where n is the number of nodes in the network and D is its diameter. The state of the art is Elkin's randomized algorithm [STOC 2017] that performs Õ(n^2/3 D^1/3 + n^5/6) rounds. We significantly improve upon this upper bound with our two new randomized algorithms for polynomially bounded integer edge weights, the first performing Õ(√n D) rounds and the second performing Õ(√n D^1/4 + n^3/5 + D) rounds. Our bounds also compare favorably to the independent result by Ghaffari and Li [STOC 2018]. As side results, we obtain a (1+ε)-approximation Õ((√n D^1/4+D)/ε)-round algorithm for directed SSSP and a new work/depth trade-off for exact SSSP on directed graphs in the PRAM model.

SODA Conference 2018 Conference Paper

Dynamic Algorithms for Graph Coloring

• Sayan Bhattacharya
• Deeparnab Chakrabarty
• Monika Henzinger
• Danupon Nanongkai

We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O (log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o (1)Δ-vertex coloring with O (polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O (log Δ) worst-case update time. This improves the recent O (Δ)-edge coloring algorithm with worst-case update time [4].

FOCS Conference 2017 Conference Paper

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n 5/4 ) Rounds

• Chien-Chung Huang 0001
• Danupon Nanongkai
• Thatchaphol Saranurak

We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits (1+o(1))-approximation Õ(n)-time algorithms [2], [3], which are matched with Ω(n)-time lower bounds [3], [4], [5] 1. No ω(n) lower bound or o(m) upper bound were known for exact computation. In this paper, we present an Õ(n 5/4 )-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are asymmetric (a. k. a. the directed case where communication is bidirectional). Our techniques also yield an Õ(n 3/4 k 1/2 + n)-time algorithm for the k-source shortest paths problem where we want every node to know distances from k sources; this improves Elkin's recent bound [6] when k = ω̃(n 1/4 ). We achieve the above results by developing distributed algorithms on top of the classic scaling technique, which we believe is used for the first time for distributed shortest paths computation. One new algorithm which might be of an independent interest is for the reversed r-sink shortest paths problem, where we want every of r sinks to know its distances from all other nodes, given that every node already knows its distance to every sink. We show an Õ(n√r)-time algorithm for this problem. Another new algorithm is called short range extension, where we show that in Õ(n√h) time the knowledge about distances can be “extended” for additional h hops. For this, we use weight rounding to introduce small additive errors which can be later fixed.

FOCS Conference 2017 Conference Paper

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

• Danupon Nanongkai
• Thatchaphol Saranurak
• Christian Wulff-Nilsen

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n o(1) ) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n 0. 5-ε ) for some constant ε > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n 0. 494 ) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n 0. 5-ε ) in [2] to O(n o(1) ) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the “contraction technique” by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.

STOC Conference 2017 Conference Paper

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n 1/2 - ε )-time

• Danupon Nanongkai
• Thatchaphol Saranurak

We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee worst-case update time and work against an adaptive adversary , meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing O (√ n ) bound of [Frederickson STOC'84, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was O (√ n (loglog n ) 2 /log n ) [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an O ( n 0.4+ o (1) ) worst-case update time, where the o (1) term hides the O (√loglog n /log n ) factor. Our second algorithm is Las Vegas and guarantee an O ( n 0.49306 ) worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by Kapron et al. To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries. The key to our results is a decomposition of graphs into subgraphs that either have high expansion or sparse. This decomposition serves as an interface between recent developments on (static) flow computation and many old ideas in dynamic graph algorithms: On the one hand, we can combine previous dynamic graph techniques to get faster dynamic spanning forest algorithms if such decomposition is given. On the other hand, we can adapt flow-related techniques (e.g. those from [Khandekar, Rao and Vazirani STOC'06], [Peng SODA'16], and [Orecchia and Zhu SODA'14]) to maintain such decomposition. To the best of our knowledge, this is the first time these flow techniques are used in fully dynamic graph algorithms.

FOCS Conference 2017 Conference Paper

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

• Parinya Chalermsook
• Marek Cygan
• Guy Kortsarz
• Bundit Laekhanukit
• Pasin Manurangsi
• Danupon Nanongkai
• Luca Trevisan 0001

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e. g. , [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i. e. , there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e. g. , this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2 o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e. g. , Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k o(1) -FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log 1/4+ε (OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

SODA Conference 2017 Conference Paper

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O (log 3 n ) Worst Case Update Time

• Sayan Bhattacharya
• Monika Henzinger
• Danupon Nanongkai

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O ( m 1/4 / ∊ 2 ), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O (1) and amortised update time O (log 2 n ), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O (1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O (log 3 n ), for all sufficiently small constants ∊.

STOC Conference 2016 Conference Paper

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

We present a deterministic (1+ o (1))-approximation O ( n 1/2+ o (1) + D 1+ o (1) )-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+ o (1))-approximation Õ( n 1/2 D 1/4 + D )-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n 1/8 , and (ii) the O (є −1 logє −1 )-approximation factor of Lenzen and Patt-Shamir’s Õ( n 1/2+є + D )-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω( n 1/2 /log n + D ) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+ o (1))-approximation O ( n 1/2+ o (1) + D 1+ o (1) )-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].

STOC Conference 2016 Conference Paper

New deterministic approximation algorithms for fully dynamic matching

• Sayan Bhattacharya
• Monika Henzinger
• Danupon Nanongkai

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O ( poly (log n , 1/є)) update time. (2) An algorithm that maintains an α K approximation of the value of the maximum matching with O ( n 2/ K ) update time in bipartite graphs, for every sufficiently large constant positive integer K . Here, 1≤ α K < 2 is a constant determined by the value of K . Result (1) is the first deterministic algorithm that can maintain an o (log n )-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O ( m 1/4 ) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

SODA Conference 2015 Conference Paper

Distributed Computation of Large-scale Graph Problems

• Hartmut Klauck
• Danupon Nanongkai
• Gopal Pandurangan
• Peter Robinson 0002

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have k machines that jointly perform computation on an arbitrary n -node (typically, n ≫ k) input graph. The graph is assumed to be randomly partitioned among the k ≥ 2 machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity, i. e. , the number of communication rounds, of solving various fundamental graph problems. We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of Ω( n/k ) rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an Ω( n / k 2 ) lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in random-partition communication complexity. To complement our lower bounds, we also give algorithms for various fundamental graph problems, e. g. , PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in Õ(n/k) time (the notation Õ hides polylog( n ) factors and an additive polylog( n ) term); this shows that one can achieve almost linear (in k ) speedup, whereas for shortest paths, we present algorithms that run in time (for (1 + ε)-factor approximation) and in time (for O (log n )-factor approximation) respectively. Our results step towards understanding the complexity of distributively solving large-scale graph problems.

STOC Conference 2015 Conference Paper

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

• Sayan Bhattacharya
• Monika Henzinger
• Danupon Nanongkai
• Charalampos E. Tsourakakis

While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.

STOC Conference 2015 Conference Paper

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai
• Thatchaphol Saranurak

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v 1 , ..., v n , one by one. After seeing each vector v i , we have to output the product Mv i before we can see the next vector. A naive algorithm can solve this problem using O(n 3 ) time in total, and its running time can be slightly improved to O(n 3 /log 2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n 3-ε )) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.

SODA Conference 2014 Conference Paper

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

We study dynamic (1 + ∊)-approximation algorithms for the single-source shortest paths problem in an unweighted undirected n -node m -edge graph under edge deletions. The fastest algorithm for this problem is an algorithm with O ( n 2+ o (1) ) total update time and constant query time by Bernstein and Roditty (SODA 2011). In this paper, we improve the total update time to O ( n 1. 8+ o (1) + m 1+ o (1) ) while keeping the query time constant. This running time is essentially tight when m = Ω( n 1. 8 ) since we need Ω( m ) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than Õ ( mn ) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee.

FOCS Conference 2014 Conference Paper

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + ε)-approximation factor, the running time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011), and more recently to O(n 1. 8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1 + ε)-approximation algorithm with O(m 1+o(1) ) total update time, thus obtaining near-linear time. Moreover, we obtain O(m 1+o(1) log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn 0. 986 log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, ε)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1 + ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E∪E'). Our algorithm can maintain an (n o(1), ε)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest.

STOC Conference 2014 Conference Paper

Distributed approximation algorithms for weighted shortest paths

• Danupon Nanongkai

A distributed network is modeled by a graph having n nodes (processors) and diameter D . We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n ) bandwidth restriction on edges (the standard synchronous CONGEST model). The question whether approximation algorithms help speed up the shortest paths and distance computation (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (SSSP) and all-pairs shortest paths (APSP) in the weighted case. Our main result is an algorithm for SSSP. Previous results are the classic O ( n )-time Bellman-Ford algorithm and an Õ ( n 1/2+1/2 k + D )-time (8 k ⌈log( k + 1)⌉ --1)-approximation algorithm, for any integer k ≥ 1, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use Õ (·) to hide the O (poly log n ) term.) We present an Õ ( n 1/2 D 1/4 + D )-time (1 + o (1))-approximation algorithm for SSSP. This algorithm is sublinear-time as long as D is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When D is small, our running time matches the lower bound of Ω ( n 1/2 + D ) by Das Sarma et al. (SICOMP 2012), which holds even when D=Θ(log n), up to a poly log n factor. As a by-product of our technique, we obtain a simple Õ ( n )-time (1+ o (1))-approximation algorithm for APSP, improving the previous Õ( n )-time O (1)-approximation algorithm following from the results of Lenzen and Patt-Shamir. We also prove a matching lower bound. Our techniques also yield an Õ ( n 1/2 ) time algorithm on fully-connected networks, which guarantees an exact solution for SSSP and a (2+ o (1))-approximate solution for APSP. All our algorithms rely on two new simple tools: light-weight algorithm for bounded-hop SSSP and shortest-path diameter reduction via shortcuts . These tools might be of an independent interest and useful in designing other distributed algorithms.

FOCS Conference 2014 Conference Paper

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs

• Parinya Chalermsook
• Bundit Laekhanukit
• Danupon Nanongkai

The study of graph products is a major research topic and typically concerns the term f(G * H), e. g. , to show that f(G * H) = f(G)f(H). In this paper, we study graph products in a non-standard form f(R[G * H]) where R is a “reduction”, a transformation of any graph into an instance of an intended optimization problem. We resolve some open problems as applications. The first problem is minimum consistent deterministic finite automaton (DFA). We show a tight n 1-ϵ approximation hardness, improving the n 1/14-ϵ hardness of [Pitt and Warmuth, STOC 1989 and JACM 1993], where n is the sample size. (In fact, we also give improved hardnesses for the case of acyclic DFA and NFA.) Due to Board and Pitt [Theoretical Computer Science 1992], this implies the hardness of properly learning DFAs assuming NP ≠ RP (the weakest possible assumption). This affirmatively answers an open problem raised 25 years ago in the paper of Pitt and Warmuth and the survey of Pitt [All 1989]. Prior to our results, this hardness only follows from the stronger hardness of improperly learning DFAs, which requires stronger assumptions, i. e. , either a cryptographic or an average case complexity assumption [Kearns and Valiant STOC 1989 and J. ACM 1994; Daniely et al. STOC 2014]. The second problem is edge-disjoint paths (EDP) on directed acyclic graphs (DAGs). This problem admits an O(√n)-approximation algorithm [Chekuri, Khanna, and Shepherd, Theory of Computing 2006] and a matching Ω(√n) integrality gap, but so far only an n 1/26-ϵ hardness factor is known [Chuzhoy et al. , STOC 2007]. (n denotes the number of vertices.) Our techniques give a tight n 1/2-ϵ hardness for EDP on DAGs, thus resolving its approximability status. As by-products of our techniques: (i) We give a tight hardness of packing vertex-disjoint k-cycles for large k, complimenting [Guruswami and Lee, ECCC 2014] and matching [Krivelevich et al. , SODA 2005 and ACM Transactions on Algorithms 2007]. (ii) We give an alternative (and perhaps simpler) proof for the hardness of properly learning DNF, CNF and intersection of halfspaces [Alekhnovich et al. , FOCS 2004 and J. Comput. Syst. Sci. 2008]. Our new concept reduces the task of proving hardnesses to merely analyzing graph product inequalities, which are often as simple as textbook exercises. This concept was inspired by, and can be viewed as a generalization of, the graph product subadditivity technique we previously introduced in SODA 2013. This more general concept might be useful in proving other hardness results as well.

STOC Conference 2014 Conference Paper

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

FOCS Conference 2013 Conference Paper

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.

SODA Conference 2013 Conference Paper

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More

• Parinya Chalermsook
• Bundit Laekhanukit
• Danupon Nanongkai

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f ( G * H ) where G and H are graphs, * is a graph product and f is a graph property. For example, if f is the independence number and * is the disjunctive product, then the product is known to be multiplicative: f ( G * H ) = f ( G ) f ( H ). In this paper, we study graph products in the following non-standard form: f (( G ⊕ H )* J ) where G, H and J are graphs, ⊕ and * are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some products ⊕ and *, it is subadditive in the sense that f (( G ⊕ H ) * J ) ≤ f ( G * J ) + f ( H * J ). Moreover, when f is the poset dimension number, it is almost subadditive. As applications of this result (we only need J = K 2 here), we obtain tight hardness of approximation for various problems in discrete mathematics and computer science: bipartite induced and semi-induced matching (a. k. a. maximum expanding sequences), poset dimension, maximum feasible subsystem with 0/1 coefficients, unit-demand min-buying and single-minded pricing, donation center location, boxicity, cubicity threshold dimension and independent packing.

FOCS Conference 2013 Conference Paper

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses

• Parinya Chalermsook
• Bundit Laekhanukit
• Danupon Nanongkai

We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the independent set problem, a question studied in the area of parameterized complexity. The second is the hardness of approximating the bipartite induced matching problem on bounded-degree bipartite graphs. The last in our series is the tight hardness of approximating the k-hypergraph pricing problem, a fundamental problem arising from the area of algorithmic game theory. In particular, assuming the Exponential Time Hypothesis, our two main results are: For any r larger than some constant, any r-approximation algorithm for the independent set problem must run in at least 2n 1-ε/ r 1+ε time. This nearly matches the upper bound of 2 n/r [23]. It also improves some hardness results in the domain of parameterized complexity (e. g. , [26], [19]). For any k larger than some constant, there is no polynomial time min{k 1-ε, n 1/2-ε } time min -approximation algorithm for the k-hypergraph pricing problem, where n is the number of vertices in an input graph. This almost matches the upper bound of min{O(k), Õ(√n) } min (by Balcan and Blum [3] and an algorithm in this paper). We note an interesting fact that, in contrast to n 1/2-ε hardness for polynomial-time algorithms, the k-hypergraph pricing problem admits n δ approximation for any δ > 0 in quasi-polynomial time. This puts this problem in a rare approximability class in which approximability thresholds can be improved significantly by allowing algorithms to run in quasi-polynomial time. The proofs of our hardness results rely on unexpectedly tight connections between the three problems. First, we establish a connection between the first and second problems by proving a new graph-theoretic property related to an induced matching number of dispersers. Then, we show that the n 1/2-ε hardness of the last problem follows from nearly tight subexponential time inapproximability of the first problem, illustrating a rare application of the second type of inapproximability result to the first one. Finally, to prove the subexponential-time inapproximability of the first problem, we construct a new PCP with several properties; it is sparse and has nearly-linear size, large degree, and small free-bit complexity. Our PCP requires no ground-breaking ideas but rather a very careful assembly of the existing ingredients in the PCP literature.

TCS Journal 2011 Journal Article

Best-order streaming model

• Atish Das Sarma
• Richard J. Lipton
• Danupon Nanongkai

We study a new model of computation, called best-order stream, for graph problems. Roughly, it is a proof system where a space-limited verifier has to verify a proof sequentially (i. e. , it reads the proof as a stream). Moreover, the proof itself is just a specific ordering of the input data. This model is closely related to many models of computation in other areas such as data streams, communication complexity, and proof checking, and could be used in applications such as cloud computing. In this paper we focus on graph problems where the input is a sequence of edges. We show that even under this model, checking some basic graph properties deterministically requires linear space in the number of nodes. We also show that, in contrast with this, randomized verifiers are powerful enough to check many graph properties in polylogarithmic space.

STOC Conference 2011 Conference Paper

Distributed verification and hardness of distributed approximation

• Atish Das Sarma
• Stephan Holzer
• Liah Kor
• Amos Korman
• Danupon Nanongkai
• Gopal Pandurangan
• David Peleg
• Roger Wattenhofer

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows in the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication.

SODA Conference 2004 Conference Paper

A deterministic near-linear time algorithm for finding minimum cuts in planar graphs

• Parinya Chalermsook
• Jittat Fakcharoenphol
• Danupon Nanongkai