Seven papers by CSE researchers presented at FOCS 2023

Seven papers by CSE researchers will be presented at the 2023 IEEE Symposium on Foundations of Computer Science (FOCS), taking place November 6-9, 2023, in Santa Cruz, CA. The flagship conference of the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF), FOCS was first founded in 1960 and remains a leading global venue for the latest findings in theoretical computer science.

The research being presented by CSE authors at FOCS offers many new contributions to this area, including a dynamic algorithm for graph matching in update time, a proposed solution for the correlation clustering problem, a novel girth concept to improve network design, and more.

The papers by U-M researchers being presented at FOCS are as follows, with authors affiliated with CSE in bold:

Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

Abstract: We show a fully dynamic algorithm for maintaining (1+ϵ)-approximate \emph{size} of maximum matching of the graph with n vertices and m edges using m0.5−Ωϵ(1) update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS ’13], [Bernstein and Stein SODA ’16],[Behnezhad and Khanna SODA ’22]).

Our key technical component is the first sublinear algorithm for (1,ϵn)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.

“All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time”

Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak

Abstract: A Gomory-Hu tree (also called a cut tree) succinctly represents $(s,t)$ min-cuts (and therefore, $(s,t)$ max-flow values) of all pairs of vertices $s, t$ in an undirected graph. In this paper, we give an $m^{1+o(1)}$-time algorithm for constructing a Gomory-Hu tree for a graph with $m$ edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud {\em et al.} (FOCS 2022) and requires $\tilde{O}(n^2)$ time for a graph with $n$ vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs max-flows problem that started with Gomory and Hu’s pathbreaking result introducing the Gomory-Hu tree in 1961.

Chasing Positive Bodies

Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak

Abstract: We study the problem of chasing positive bodies in ℓ1: given a sequence of bodies Kt={xt∈ℝn+∣Ctxt≥1,Ptxt≤1} revealed online, where Ct and Pt are nonnegative matrices, the goal is to (approximately) maintain a point xt∈Kt such that ∑t‖xt−xt−1‖1 is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.

We give an O(logd)-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix Ct. This bypasses and improves exponentially over the lower bound of √n known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless.

We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering

Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman

Abstract: We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either + or −, the goal is to find a partition of the vertices that minimizes the number of the \pedges across parts plus the number of the \medges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15].

We significantly improve the state-of-the-art by providing a 1.73-approximation for the problem. Our approach introduces a preclustering of Correlation Clustering instances that allows us to essentially ignore the error arising from the {\em correlated rounding} used by [CLN22]. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new {\em set-based rounding} that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound.

Bridge Girth: A Unifying Notion in Network Design

Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi

A classic 1993 paper by Althőfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function γ of high-girth graphs. This paper initiated a large body of work in network design, in which problems are attacked by reduction to γ or the analogous extremal function for other girth concepts. In this paper, we introduce and study a new girth concept that we call the bridge girth of path systems, and we show that it can be used to significantly expand and improve this web of connections between girth problems and network design. We prove two kinds of results:

1) We write the maximum possible size of an n-node, p-path system with bridge girth >k as β(n,p,k), and we write a certain variant for “ordered” path systems as β^∗(n,p,k). We identify several arguments in the literature that implicitly show upper or lower bounds on β,β^∗, and we provide some polynomially improvements to these bounds. In particular, we construct a tight lower bound for β(n,p,2), and we polynomially improve the upper bounds for β(n,p,4) and β^∗(n,p,∞).

2) We show that many state-of-the-art results in network design can be recovered or improved via black-box reductions to β or β^∗. Examples include bounds for distance/reachability preservers, exact hopsets, shortcut sets, the flow-cut gaps for directed multicut and sparsest cut, an integrality gap for directed Steiner forest.

We believe that the concept of bridge girth can lead to a stronger and more organized map of the research area. Towards this, we leave many open problems, related to both bridge girth reductions and extremal bounds on the size of path systems with high bridge girth.

On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

Suprovat Ghoshal, Euiwoong Lee

Abstract: A 𝜇-constrained Boolean Max-CSP(𝜓) instance is a Boolean Max-CSP instance on predicate 𝜓 : {0,1}^𝑟 ⟶ {0,1} where the objective is to find a labeling of relative weight exactly 

that maximizes the fraction of satisfied constraints. In this work, we study the approximability of constrained Boolean Max-CSPs via SDP hierarchies by relating the integrality gap of Max-CSP(𝜓) to its 𝜇-dependent approximation curve. Formally, assuming the Small-Set Expansion Hypothesis, we show that it is NP-hard to approximate 𝜇-constrained instances of Max-CSP(𝜓) up to factor Gap_𝑙,𝜇(𝜓)/log(1/𝜇)² (ignoring factors depending on 𝑟) for any 𝑙 ≥ 𝑙 (𝜇,𝑟). Here, Gap_𝑙,𝜇(𝜓) is the optimal integrality gap of 𝑙-round Lasserre relaxation for 𝜇-constrained Max-CSP(𝜓) instances. Our results are derived by combining the framework of Raghavendra [STOC 2008] along with more recent advances in rounding Lasserre relaxations and reductions from the Small-Set Expansion (SSE) problem. A crucial component of our reduction is a novel way of composing generic bias-dependent dictatorship tests with SSE, which could be of independent interest.

Folklore Sampling is Optimal for Exact Hopsets: Confirming the √𝑛 Barrier

Greg Bodwin, Gary Hoppenworth

Abstract: For a graph G, a D-diameter-reducing exact hopset is a small set of additional edges H that, when added to G, maintains its graph metric but guarantees that all node pairs have a shortest path in G∪H using at most D edges. A shortcut set is the analogous concept for reachability. These objects have been studied since the early ’90s due to applications in parallel, distributed, dynamic, and streaming graph algorithms.

For most of their history, the state-of-the-art construction for either object was a simple folklore algorithm, based on randomly sampling nodes to hit long paths in the graph. However, recent breakthroughs of Kogan and Parter [SODA ’22] and Bernstein and Wein [SODA ’23] have finally improved over the folklore diameter bound of Õ(n^1/2) for shortcut sets and for (1+ϵ)-approximate hopsets. For both objects it is now known that one can use O(n) hop-edges to reduce diameter to Õ(n^1/3). The only setting where folklore sampling remains unimproved is for exact hopsets. Can these improvements be continued?

We settle this question negatively by constructing graphs on which any exact hopset of O(n) edges has diameter Ω̃(n^1/2). This improves on the previous lower bound of Ω̃(n^1/3) by Kogan and Parter [FOCS ’22]. Using similar ideas, we also polynomially improve the current lower bounds for shortcut sets, constructing graphs on which any shortcut set of O(n) edges reduces diameter to Ω̃(n^1/4). This improves on the previous lower bound of Ω(n^1/6) by Huang and Pettie [SIAM J. Disc. Math. ’18]. We also extend our constructions to provide lower bounds against O(p)-size exact hopsets and shortcut sets for other values of p; in particular, we show that folklore sampling is near-optimal for exact hopsets in the entire range of p∈[1,n²].