CS Paper Radar

A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability

Zhijie Zheng

cs.DS ·submitted 2026-10-30 13:22 UTC · v1

Abstract

We give a fully polynomial randomized approximation scheme for all-terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank. The algorithm estimates the probability that independent hyperedge failures disconnect the hypergraph, allowing a different rational failure probability for every edge. For a common failure probability, this improves the quasi-polynomial approximation schemes of Cen, Li, and Panigrahi to polynomial time and answers the polynomial-time approximation question reiterated in their subsequent work on graphs. The construction turns their representative-survival bound into an importance sampler whose relative second moment is bounded solely in terms of the number of vertices. We protect one randomly chosen representative pair during contraction, correct the path likelihood, and divide by the number of pairs surviving at the end. The resulting unbiased estimator has relative second moment at most $\binom n2$, even when unreliability is exponentially small. A minimum-cut normalization makes this estimator implementable with polynomially bounded precision: the residual likelihood becomes a survival probability in an auxiliary absorbing process, which admits rational discretization with a fixed random-bit budget. Logarithmic rate rounding and an exact weighted minimum cut extend the construction to unequal rational failure probabilities. The algorithm's worst-case running time and random-bit usage are polynomial in the input length, the inverse relative error, and $\log(1/δ)$ for confidence $1-δ$.

Comment
19 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.66
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Optimal Sample Complexity for Max-Cut

cs.DS ·2026-11-02 ·Itamar Bender, Robert Krauthgamer
theory similarity 0.66
Abstract

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.

0.21

Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs

cs.DS ·2026-08-20 ·Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri
theory similarity 0.66
Abstract

We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $Ω(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.

0.22

Property B for random non-uniform hypergraphs

cs.DM math.COmath.PR ·2026-10-05 ·Grzegorz Ryn, Jakub Kozik
similarity 0.64
Abstract

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

0.16

Stochastic Matching with Polynomial Degree

cs.DS ·2026-11-02 ·Soheil Behnezhad
hot direction similarity 0.62
Abstract

We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

0.23

Instance-Optimality of Single-Pair Personalized PageRank

cs.DS ·2026-11-09 ·Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan
similarity 0.62
Abstract

We consider discounted random walks in a directed simple graph $G=(V,E)$. Such a walk terminates at each step with a constant probability $α\in (0,1)$ and otherwise continues to a uniform random out-neighbor. Given a pair $(s,t)\in V^2$, we denote by $π(s,t)$ the probability of such a discounted random walk starting at $s$ terminates at $t$. This probability is referred to as the Personalized PageRank (PPR) of $t$ with respect to $s$. The problem of estimating $π(s,t)$ within a constant multiplicative factor with constant success probability for a given vertex pair $(s,t)$ is called the single-pair PPR estimation problem. We investigate the instance-optimality of single-pair PPR estimation in directed graphs. We present a new algorithm that aims at instance-optimal running time up to polylogarithmic factors. In other words, no correct algorithm can run faster than our algorithm on any valid graph by more than a polylogarithmic factor. We show that our algorithm is instance-optimal in the standard adjacency-list query model if $n$ is not known (as is often the case for most of the large networks to which PPR is applied). When $n$ is known, our algorithm is still instance-optimal for sparse graphs. For denser graphs, when $n$ is known, we show that no algorithm can achieve general instance-optimality. For the multiplicative approximation of PPR, we also improve the worst-case complexity from $O(mn\log n)$ to the near-optimal $O(m\log n)$. This is not only for the single-pair discussed above, but also for the single-source and single-target variants of the PPR estimation problem.

0.08

Graph Spectral Sparsification is in Catalytic Logspace

cs.DS cs.CC ·2026-08-21 ·Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
similarity 0.62
Abstract · 29 pages

We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm outputs an $\varepsilon$-spectral sparsifier of $G$ with $O(n\varepsilon^{-2}\log n)$ edges, matching the effective resistance sampling of Spielman and Srivastava (STOC 2008). This gives a new, natural problem in catalytic logspace that is not known to be in deterministic $\mathbf{NC}$ or $\mathbf{SC}$. Our main contribution is an entirely new technique in the compress--or--random paradigm for catalytic logspace that we believe will have further applications. We first analyze effective-resistance sparsification using a pessimistic estimator that can itself be computed in catalytic logspace. The estimator is motivated by the viewpoint of graph quasirandomness and immediately gives a simple, deterministic greedy algorithm for graph sparsification. Subsequently, we show that such a pessimistic estimator can be transformed into an algorithm that performs an in-place compression of a string with bad potential. Our algorithm is based on using the potential function to define a measure over strings, and implementing arithmetic coding using this measure in-place. This compression technique is substantially distinct from all prior tools in the field of catalytic computation.

0.20

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.62
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10