Yu Chen 0039

SODA Conference 2025 Conference Paper

Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

• Yu Chen 0039
• Zihan Tan

SODA Conference 2024 Conference Paper

An Ω~(√log|T|) Lower Bound for Steiner Point Removal

• Yu Chen 0039
• Zihan Tan

SODA Conference 2024 Conference Paper

On (1 + ɛ)-Approximate Flow Sparsifiers

• Yu Chen 0039
• Zihan Tan

Given a large graph G with a subset | T | = k of its vertices called terminals, a quality-q flow sparsifier is a small graph G’ that contains T and preserves all multicommodity flows that can be routed between terminals in T, to within factor q. The problem of constructing flow sparsifiers with good (small) quality and (small) size has been a central problem in graph compression for decades. A natural approach of constructing O (1)-quality flow sparsifiers, which was adopted in most previous constructions, is contraction. Andoni, Krauthgamer, and Gupta constructed a sketch of size f (k, ɛ) that stores all feasible multicommodity flows up to a factor of (1 + ɛ), raised the question of constructing quality- (1 + ɛ) flow sparsifiers whose size only depends on k, ɛ (but not the number of vertices in the input graph G ), and proposed a contraction-based framework towards it using their sketch result. In this paper, we settle their question for contraction-based flow sparsifiers, by showing that quality-(1 + ɛ) contraction-based flow sparsifiers with size f (ɛ) exist for all 5-terminal graphs, but not for all 6-terminal graphs. Our hardness result on 6-terminal graphs improves upon a recent hardness result by Krauthgamer and Mosenzon on exact (quality-1) flow sparsifiers, for contraction-based constructions. Our construction and proof utilize the notion of tight spans in metric geometry, which we believe is a powerful tool for future work.

SODA Conference 2023 Conference Paper

Query Complexity of the Metric Steiner Tree Problem

• Yu Chen 0039
• Sanjeev Khanna
• Zihan Tan

In the metric Steiner Tree problem, we are given an n × n metric w on a set V of vertices along with a set T ⊆ V of k terminals, and the goal is to find a tree of minimum cost that contains all terminals in T. This is a well-known NP-hard problem and much of the previous work has focused on understanding its polynomial-time approximability. In this work, we initiate a study of the query complexity of the metric Steiner Tree problem. Specifically, if we desire an α-approximate estimate of the metric Steiner Tree cost, how many entries need to be queried in the metric w? For the related minimum spanning tree (MST) problem, this question is well-understood. For any fixed ε > 0, one can estimate the MST cost to within a (1 + ε)-factor using only Õ ( n ) queries, and this is known to be essentially tight. Can one obtain a similar result for Steiner Tree cost? Note that a (2 + ε)-approximate estimate of Steiner Tree cost can be obtained with Õ ( k ) queries by simply applying the MST cost estimation algorithm on the metric induced by the terminals. Our first result shows that the Steiner Tree problem behaves in a fundamentally different manner from MST: any (randomized) algorithm that estimates the Steiner Tree cost to within a (5/3 — ε)-factor requires Ω( n 2 ) queries, even if k is a constant. This lower bound is in sharp contrast to an upper bound of O(nk) queries for computing a (5/3)-approximate Steiner Tree, which follows from previous work by Du and Zelikovsky. Our second main result, and the main technical contribution of this work, is a sublinear query algorithm for estimating the Steiner Tree cost to within a strictly better-than -2 factor. We give an algorithm that achieves this goal, with a query complexity of Õ ( n 12/7 + n 6/7 · k ); since k ≤ n, the algorithm performs at most O ( n 13/7 ) = o ( n 2 ) queries in the worst-case. Our estimation algorithm reduces this task to that of designing a sublinear query algorithm for a suitable set cover problem. We complement this result by showing an query lower bound for any algorithm that estimates Steiner Tree cost to a strictly better than 2 factor. Thus queries are needed to just beat 2-approximation when k = Ω ( n ); a sharp contrast to MST cost estimation where a (1 + o (1))-approximate estimate of cost is achievable with only Õ ( n ) queries. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 03893

FOCS Conference 2022 Conference Paper

On Weighted Graph Sparsification by Linear Sketching

• Yu Chen 0039
• Sanjeev Khanna
• Huan Li 0002

A seminal work of [Ahn-Guha-McGregor, PODS’12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS’14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA’21]. All these linear sketching algorithms, however, only work on unweighted graphs, and are extended to weighted graphs by weight grouping, a non-linear operation not implementable in, for instance, general turnstile streams. In this paper, we initiate the study of weighted graph sparsification by linear sketching by investigating a natural class of linear sketches that we call incidence sketches, in which each measurement is a linear combination of the weights of edges incident on a single vertex. This class captures all aforementioned linear sketches for unweighted sparsification. It also covers linear sketches implementable in the simultaneous communication model, where edges are distributed across n machines. Our results are: 1)Weighted cut sparsification: We give an algorithm that computes a $(1+\epsilon)$-cut sparsifier using $\tilde{O}(n\epsilon^{-3})$ linear measurements, which is nearly optimal. This also implies a turnstile streaming algorithm with $\tilde{O}(n\epsilon^{-3})$ space. Our algorithm is achieved by building a so-called “weighted edge sampler” for each vertex. 2)Weighted spectral sparsification: We give an algorithm that computes a $(1+\epsilon)$-spectral sparsifier using $\tilde{O}(n^{6/5}\epsilon^{-4})$ linear measurements. This also implies a turnstile streaming algorithm with $\tilde{O}(n^{6/5}\epsilon^{-4})$ space. Key to our algorithm is a novel analysis of how the effective resistances change under vertex sampling. Complementing our algorithm, we then prove a superlinear lower bound of $\Omega(n^{21/20-o(1)})$ measurements for computing some O(1)-spectral sparsifier using incidence sketches. 3)Weighted spanner computation: We first show that any $o(n^{2})$ linear measurements can only recover a spanner of stretch that in general depends linearly on $\frac{w_{\max}}{w_{\min}}$. We thus focus on graphs with $\frac{w_{\max}}{w_{\min}}=O(1)$ and study the stretch’s dependence on n. On such graphs, the algorithm in [FiltserKapralov-Nouri, SODA’21] can obtain a spanner of stretch $\tilde{O}\left(n^{\frac{2}{3}\left(1-\alpha\right)}\right)$ using $\tilde{O}(n^{1+\alpha})$ measurements for any $\alpha\in [0, 1]$. We prove that, for incidence sketches, this tradeoff is optimal up to an $n^{o(1)}$ factor for all $\alpha\lt 1/10$. We prove both our lower bounds by analyzing the “effective resistances” in certain matrix-weighted graphs, where we develop a number of new tools for reasoning about such graphs – most notably (i) a matrix-weighted analog of the widely used expander decomposition of ordinary graphs, and (ii) a proof that a random vertex-induced subgraph of a matrix-weighted expander is also an expander. We believe these tools are of independent interest.

FOCS Conference 2021 Conference Paper

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

• Deeparnab Chakrabarty
• Yu Chen 0039
• Sanjeev Khanna

The problem of minimizing a submodular function (SFM) is a common generalization of several fundamental combinatorial optimization problems, including minimum $s-t$ cuts in graphs and matroid intersection. It is well-known that a submodular function can be minimized with only $\text{poly} (N)$ function evaluation queries where $N$ denotes the universe size. However, all known polynomial query algorithms for SFM are highly adaptive, requiring at least $N$ rounds of adaptivity. A natural question is if SFM can be efficiently solved in a highly parallel manner, namely, with $\text{poly} (N)$ queries using only poly-logarithmic rounds of adaptivity. An important step towards understanding the adaptivity needed to solve SFM efficiently was taken in the very recent work of Balkanski and Singer who showed that any SFM algorithm with $\text{poly} (N)$ queries. This left open the possibility of efficient SFM algorithms with poly-logarithmic rounds of adaptivity. In this work, we strongly rule out this possibility by showing that any, possibly randomized, algorithm for submodular function minimization making $\text{poly} (N)$ queries requires $\tilde{\Omega}(N^{1/3})$ rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make up to $2^{N^{1-\delta}}$ queries, for any constant $\delta > 0$.

FOCS Conference 2020 Conference Paper

Near-linear Size Hypergraph Cut Sparsifiers

• Yu Chen 0039
• Sanjeev Khanna
• Ansh Nagda

Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any $n$ -vertex undirected weighted graph $G$ and a parameter $\varepsilon\in(0, 1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G^{\prime}$ of $G$ of size $\tilde{O}(n/\varepsilon^{2})$ such that the weight of every cut in $G$ is preserved to within a ( $1\pm\varepsilon$ )-factor in $G^{\prime}$. The graph $G^{\prime}$ is referred to as a ( $1\pm\varepsilon$ )-approximate cut sparsifier of $G$. A natural question is if such cut-preserving sparsifiers also exist for hypergraphs. Kogan and Krauthgamer (2015) initiated a study of this question and showed that given any weighted hypergraph $H$ where the cardinality of each hyperedge is bounded by $r$, there is a polynomial-time algorithm to find a ( $1\pm\varepsilon$ )-approximate cut sparsifier of $H$ of size $\tilde{O}(\frac{nr}{\varepsilon^{2}})$. Since $r$ can be as large as $n$, in general, this gives a hypergraph cut sparsifier of size $\tilde{O}(n^{2}/\varepsilon^{2})$, which is a factor $n$ larger than the Benczúr-Karger bound for graphs. It has been an open question whether or not Benczúr-Karger bound is achievable on hypergraphs. In this work, we resolve this question in the affirmative by giving a new polynomial-time algorithm for creating hypergraph sparsifiers of size $\tilde{O}(n/\varepsilon^{2})$.

STOC Conference 2019 Conference Paper

Polynomial pass lower bounds for graph streaming algorithms

• Sepehr Assadi
• Yu Chen 0039
• Sanjeev Khanna

We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum s - t cut in an n -vertex undirected graph requires n 2− o (1) space unless it makes n Ω(1) passes over the stream.

SODA Conference 2019 Conference Paper

Sublinear Algorithms for (Δ + 1) Vertex Coloring

• Sepehr Assadi
• Yu Chen 0039
• Sanjeev Khanna

Any graph with maximum degree Δ admits a proper vertex coloring with Δ+1 colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We answer this fundamental question in the affirmative for several canonical classes of sublinear algorithms including graph streaming, sublinear time, and massively parallel computation (MPC) algorithms. In particular, we design: A single-pass semi-streaming algorithm in dynamic streams using Õ ( n ) space. The only known semi-streaming algorithm prior to our work was a folklore O (log n )-pass algorithm obtained by simulating classical distributed algorithms in the streaming model. A sublinear-time algorithm in the standard query model that allows neighbor queries and pair queries using time. We further show that any algorithm that outputs a valid coloring with sufficiently large constant probability requires time. No non-trivial sublinear time algorithms were known prior to our work. A parallel algorithm in the massively parallel computation (MPC) model using Õ ( n ) memory per machine and O (1) MPC rounds. Our number of rounds significantly improves upon the recent O (log log Δ · log* ( n ))-round algorithm of Parter [ICALP 2018]. At the core of our results is a remarkably simple meta-algorithm for the (Δ + 1) coloring problem: Sample O (log n ) colors for each vertex independently and uniformly at random from the Δ + 1 colors; find a proper coloring of the graph using only the sampled colors of each vertex. As our main result, we prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in each model. We note that all our upper bound results for (Δ + 1) coloring are either optimal or close to best possible in each model studied. We also establish new lower bounds that rule out the possibility of achieving similar results in these models for the closely related problems of maximal independent set and maximal matching. Collectively, our results highlight a sharp contrast between the complexity of (Δ+1) coloring vs maximal independent set and maximal matching in various models of sublinear computation even though all three problems are solvable by a simple greedy algorithm in the classical setting.