CS Paper Radar

Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time

Jingcheng Liu, Yitong Yin

cs.DS ·submitted 2026-11-04 15:33 UTC · v1

Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximating Independent Sets Using Additive Combinatorics

cs.DS cs.CCmath.CO ·2026-10-18 ·Shachar Lovett
published similarity 0.68
Abstract

We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.

0.60

Query Complexity of Densest Sub(hyper)graph Problems

cs.DS cs.CC ·2026-10-13 ·Sinan G. Aksoy, Eli Friedman, Nate Veldt, Stephen J. Young
theory similarity 0.68
Abstract · 26 pages

Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries. In this work, we examine the query complexity of densest subgraph problems. Our first contribution is to generalize the uniform sparsification approach for Densest Subgraph and other heavy subgraph problems to weighted graphs, achieving the following results. >A $(1+\varepsilon)$-approximation for weighted Densest Subgraph in $O(n\log^2 n/\varepsilon^2)$ queries, roughly matching the $Ω(n/\log n)$ lower bound we prove for randomized algorithms. >A $(1+\varepsilon)$-approximation for weighted Max Cut in $O(n\log^2 n/\varepsilon^2)$ queries. This improves upon the bound of $O(n\log^3 n(\log n+1/\varepsilon^2))$ queries achieved by Plevrakis et al., making significant progress towards their lower bound of $Ω(n/\log n)$ queries. In contrast, we rule out approximation schemes with truly subquadratic query complexity for Densest $k$-Subgraph and settle its exact query complexity in both the unweighted and deterministic settings. For hypergraphs, we show CUT queries alone cannot achieve $o(\sqrt{n})$-approximation for Densest Subhypergraph or $o(n)$-approximation for Densest $k$-Subhypergraph, regardless of the number of queries. Augmenting CUT queries with the EDGE oracle of Chen et al., we overcome this barrier for Densest Subhypergraph and obtain a $(1+\varepsilon)$-approximation on rank-$r$ hypergraphs using $O(nr\log n/\varepsilon^2)$ queries. We also extend our Densest $k$-Subgraph hardness results to hypergraphs and prove exponential query lower bounds for exact Densest $k$-Subhypergraph. Lastly, confirming a conjecture of Chakrabarty and Liao, we show that simulating an ADD query using CUT and IS-EDGE$^?$ queries requires exponentially-many queries.

0.24

Fine-Grained Complexity Across the Computational Phase Transition

cs.CC cs.DSmath.PR ·2026-11-02 ·Zhe Ju, Jingcheng Liu, Yitong Yin
theory similarity 0.66
Abstract

How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.

0.50

Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally

cs.DS ·2026-11-02 ·Mengyang Wu, Minghao Wang
theoryhot direction similarity 0.65
Abstract · 27 pages

Assuming a Boolean tensor contraction hypothesis (Theorem D.1 of OpenAI's recent preprint refuting the Exponential Time Hypothesis), we study exact feedback vertex set counting in general graphs. For an $n$-vertex, $m$-edge simple graph, we compute the complete size distribution deterministically in $\mathrm{poly}(n+m)\,2^{O(n(\log\log n)^2/\sqrt{\log n})}$ time and polynomial working space. The algorithm combines a whole-edge forest identity, subset-index scalar networks, sparse parity filtering, and disjoint high-degree branching. A binomial inversion recovers the multiplicities introduced by exceptional-set guesses. The counting interface supports fixed vertices, minimum solutions, and unranking. Component markers yield induced-tree and induced-path counts within the same bound. Sparse Hamilton, forest, and Steiner edge-tree counting follow from the scalar encoding.

0.38

Better Bounds For Graph Reconstruction

cs.DS cs.DM ·2026-11-09 ·Antoni Buraczewski, Paweł Gawrychowski
publishedtheory similarity 0.65
Abstract · in FOCS 2026

The goal in graph reconstruction problems is to learn an initially unknown graph using only a few queries of a specific type. Possibly the most natural query type is retrieving the distance between any two vertices of a connected, undirected, and unweighted graph. For a bounded-degree graph on $n$ vertices, Kannan, Mathieu, and Zhou [TALG 2018] showed a randomized algorithm that uses only $\tilde{\mathcal{O}}(n^{3/2})$ such queries. On the lower bound side, it is only known that any randomized algorithm needs $Ω(n\log n)$ queries. We make a significant step forward to bridging these bounds by designing a randomized algorithm that uses $n^{4/3+o(1)}$ queries. This requires extending the original approach based on Voronoi diagrams into a recursive procedure that partitions a cell into smaller cells. While such a recursive approach has been used in the related graph verification problem, in the more general graph reconstruction problem we need to operate without knowing the graph, which requires a new (and more technical) approach.

0.21

Optimal Sample Complexity for Max-Cut

cs.DS ·2026-11-02 ·Itamar Bender, Robert Krauthgamer
theory similarity 0.65
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

A Linear-Time Approximation Scheme for the Densest Subgraph Problem

cs.DS ·2026-08-11 ·Elena Grigorescu, Mehrshad Taziki
similarity 0.64
Abstract

In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

0.04

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.64
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21