CS Paper Radar

The Limits of Black-Box Reductions for All-Pairs Triangle Detection

Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

cs.DS cs.CC ·submitted 2026-08-19 16:42 UTC · v1
theory

Abstract

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

Comment
32 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings

cs.DM cs.CCmath.CO ·2026-09-25 ·Péter Madarasi, Máté Simon
theory similarity 0.65
Abstract

For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.

0.23

Tolerant Testers for Subgraph-Freeness

cs.DS ·2026-10-14 ·Reut Levi, Jonathan Meiri
published similarity 0.64
Abstract

In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

0.32

Real-to-Integer Reduction for All-Pairs Shortest Paths

cs.DS ·2026-11-03 ·Nick Fischer, Adam Polak, Jonas Schmidt
theory similarity 0.63
Abstract

Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.

0.05

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

cs.DS cs.CC ·2026-10-05 ·Josh Alman, Virginia Vassilevska Williams
highly cited similarity 0.62
Abstract · 76 pages

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

0.51

Metric Planarity Testing is Hard

cs.DS ·2026-10-11 ·Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak, Hung Le, Bartłomiej Lewandowski +1 more
theory similarity 0.62
Abstract · 9 figures, 27 pages

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+ε)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $ε\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+ε)$.

0.29

When is greedy exact for weighted minimum 3-cut?

cs.DS ·2026-10-26 ·Armando Rodado Amaris
theorycode/data similarity 0.61
Abstract · 16 pages. Lean 4 proofs and Python reproduction scripts are provided as ancillary files and at https://github.com/armandorodado/minimum-3cut…

The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.

0.44

Scalable Triangle Counting: The Threshold Algorithm

cs.DS cs.DB ·2026-09-14 ·Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor
hot direction similarity 0.60
Abstract

We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm---read edges from the stream until $Q$ triangles are observed in the prefix, then output $Q\,(m/S)^3$ where $S$ is the stopping length---and prove that, when the maximum number of triangles incident to any edge satisfies $η\le T^{2/3}$, this is a $(1\pm\varepsilon)$-approximation of $T$ with probability $1-δ$ using $O(\varepsilon^{-2}\log(1/δ)\, m/T^{1/3})$ memory. Crucially, the algorithm does not need any a priori estimate of $T$, in sharp contrast with state-of-the-art sampling-rate based algorithms (McGregor and Vorotnikova, PODS 2020; Tsourakakis et al., KDD 2009). It also does not need a prescribed memory budget: the stopping rule self-selects the prefix length and can return an estimate before reading the entire stream. The proof rests on a Schudy--Sviridenko concentration argument for an independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. On six real temporal streams, the algorithm's stopping prefix follows the predicted cube-root scaling and achieves at most $6\%$ error at a $10\%$ prefix, without using $T$. At a fixed stored-edge budget, variance-reduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, $1.8\times10^9$-edge graph, the threshold algorithm reads $0.46\%$ of the stream and returns $3.8\%$ error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap.

0.34

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

cs.DS ·2026-09-25 ·Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka
similarity 0.60
Abstract

Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

0.32