CS Paper Radar

The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation

Chenglin Fan, Wonseok Shin

cs.DS ·submitted 2026-10-10 05:43 UTC · v1

Abstract

Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query complexity of estimating the number of edges $m$ and the degree moments $M_s = \sum_{v \in V} (d_v)^s$ for fixed integers $s \ge 2$. In this model, [Beretta and Tětek, TALG 2024] estimate $m$ within relative error $\varepsilon$ using $O(\log n/\varepsilon^2+\sqrt n/\varepsilon)$ expected queries without knowing the number of vertices $n$, and [Bhattacharya and Pradhan, CIAC 2025] estimate $M_s$ using $O(n^{1-1/s}/\varepsilon^2)$ queries when $n$ is given. We show that the query complexity of both problems is governed by the matching number $ν$ of $G$ (the maximum number of pairwise disjoint edges) rather than the number of vertices $n$, and that the dependence on $\varepsilon$ for degree moments can be polynomially improved. Our algorithms rest on a simple observation: the endpoints of a maximum matching cover every edge, so a random endpoint of a random edge falls on this set of $2ν$ vertices with probability at least $1/2$. For every $\varepsilon\in(0,1]$, we give advice-free algorithms that estimate $m$ and $M_s$ within relative error $\varepsilon$ with probability at least $2/3$, without knowledge of $n$, $ν$, or other graph parameters. Specifically, our algorithms use $O(\min\{ν/\varepsilon, 1/\varepsilon^2+\sqrtν/\varepsilon\})$ expected queries for $m$ and $O(\min\{ν^{1-1/s}/\varepsilon^{2/s}, ν^{1-1/(2s-1)}/\varepsilon^{2/(2s-1)}\})$ for $M_s$. Finally, our lower bounds show that for every $k \ge 2$ and sufficiently small $\varepsilon$, these query complexities are optimal up to constant factors over graphs with matching number at most $k$.

Comment
46 pages; abstract shortened for arXiv

Closest papers

Nearest neighbours by meaning across the whole index.

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

Uniformity Testing for the Monomer-Dimer Model

cs.DS cs.DM ·2026-10-27 ·Joy Qiping Yang, Yuichi Yoshida
top venuetheory similarity 0.67
Abstract · To appear in SODA 2027

We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.

0.42

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

cs.LG stat.ML ·2026-09-27 ·Soham Dan
theory similarity 0.65
Abstract

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

0.18

Sampling Matchings in Near-linear Time

cs.DS ·2026-09-18 ·Tianshun Miao, Yitong Yin
theory similarity 0.65
Abstract

For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

0.38

Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries

cs.DS ·2026-11-04 ·Edith Cohen, Mohammad Roghani
theory similarity 0.64
Abstract

A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For $n$-vertex graphs of maximum degree $Δ\ge2$, Levi et al. [Algorithmica'17] give a $(1-\varepsilon)$-approximate matching LCA using $(Δ/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n)$ queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error $\varepsilon n$ using $Δ^{O(1/\varepsilon^2)}$ queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a $Δ^{Ω(1/\varepsilon)}$ lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive $\varepsilon n$ error. This leaves a gap between linear and quadratic dependence on $1/\varepsilon$ in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with $Δ^{O(1/\varepsilon)}$ queries for a $(1-\varepsilon)$-approximate matching, and an estimator for the maximum matching size within $\varepsilon n$ using $Δ^{O(1/\varepsilon)}$ queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs $O(\varepsilon^{-1}\logΔ)$ rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.

0.17

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.64
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

Stochastic Matching with Polynomial Degree

cs.DS ·2026-11-02 ·Soheil Behnezhad
hot direction similarity 0.64
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

Finding and Certifying Weighted Minimum Cuts with Cut Queries

cs.DS ·2026-11-02 ·Troy Lee
similarity 0.62
Abstract · 57 pages. v2: corrects cross-reference names (some lemmas, remarks, definitions and corollaries were labelled "Theorem"); no change in conte…

We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.

0.25