PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster Sublinear Maximal Independent Set Size

Peter Kiss, Arash Kooroshnezhad

arXiv:2610.03588v1cs.DS

TL;DR

Estimating the size of a maximal independent set sublinearly is difficult in a regime where prior sampling and membership methods require about n^1.5 time. The paper adapts the internal recursive membership procedure to use a partially computed independent set, achieving an expected ˜O(n^1+1/3) running time and applications to metric clustering and Steiner forest.

  • Problem

    Estimating the size of a maximal independent set within a (1 + ϵ) factor is a sublinear-time problem, and the hard regime yields an Ω(n^1+1/2) cost for repeated sampling and membership tests.

    Source: §1 · pp. 1–2

  • Method

    The algorithm adapts the recursive membership procedure to be initialized with and guided by a partially computed maximal independent set.

    Source: §1 · p. 2

  • Results

    ˜O(n^1+1/3) expected running time gives a (1 + ϵ)-approximation to the random-order greedy MIS size, improving on the Ω(n^1+1/2) hard-regime bound.

    Source: §1 · p. 2, §1.1 · p. 3

  • Takeaways & Limitations

    The estimator accelerates the metric Steiner forest algorithm of Mahabadi et al. [MRTV26] and supports a bi-criteria k-center estimate in general metrics.

    Source: §1 · p. 3

    The query-complexity analysis is conditioned on the residual-degree-bound event and on the permutation prefix through π−1(i0).

    Source: §4 · p. 9

Abstract

from arXiv · show

We give a sublinear-time algorithm for estimating the size of a maximal independent set in a graph using adjacency-query access with expected running time $\tilde{O}(n^{1+1/3})$, improving over the previous $\tilde{O}(n^{1+1/2})$ bound of Mahadabi et al. [MRTV26]. As a consequence of a reduction of [MRTV26], this also improves the running time for sublinear metric Steiner forest. We further show that a bi-criteria estimate of the $k$-center objective in general metrics can be obtained via a reduction to maximal independent set size estimation.

1 Introduction

Maximal independent sets are important across graph algorithms, but estimating their size sublinearly faces a hard regime where existing sampling and membership methods require about n^1.5 time. This work breaks that barrier with a faster estimator and applies it to metric Steiner forest and general-metric k-center.

1 Introduction

  • In the hard regime, a random vertex belongs to the MIS with probability about 1/√n, while each membership query costs ˜O(n), yielding an Ω(n^1+1/2) barrier.Explicit construction is also too expensive when the output MIS is roughly √n.Source: §1 · p. 2
  • Expected running time ˜O(n^1+1/3) gives a (1 + ϵ)-approximation to the size of the random-order greedy maximal independent set.The guarantee is for adjacency-matrix query access and holds with high probability.Source: §1 · p. 2, §1.1 · p. 3

1.1 Technical Overview

  • Guiding the membership procedure with S_b avoids treating the oracle as a black box and supports an expected total sampling cost of ˜O(n^1+1/3).The partially computed set helps test whether sampled vertices are in S_b, dominated by S_b, or potentially in U.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

  • The improved estimator accelerates the O(log k)-approximation for metric Steiner forest of Mahabadi et al. [MRTV26].Their algorithm's running time is proportional to the cost of estimating MIS size.Source: §1 · p. 3
  • For general metrics, combining MIS-size estimation with a threshold-graph algorithm estimates the k-center radius within 2 + ϵ using at most (1 + ϵ)k centers.The passage states that a bi-criteria relaxation is necessary for sublinear dependence on nk, since constant-factor non-bi-criteria approximation requires Ω(nk) distance queries.Source: §1 · p. 3

1.1 Technical Overview

  • The algorithm estimates the size of the independent set produced by random-order greedy, first computing baseline independent set Sb by running greedy on a random vertex permutation until Θ(n1+1/3) adjacency-matrix queries have been made.U is the set of vertices not yet dominated by Sb; λ is the length of the longest chain of vertices not added to Sb.Source: §1.1 · p. 3

2 Preliminaries

The paper studies estimating the size of the greedy maximal independent set, using adjacency-matrix access and vertex-membership oracles. It fixes the graph notation and defines the random-order greedy process used throughout.

2 Preliminaries

  • A maximal independent set cannot be enlarged while remaining independent; equivalently, every vertex outside it has a neighbor in it.The paper uses “banned” for what is commonly called dominated.Source: §2 · p. 4
  • The random-order greedy algorithm processes vertices in a uniformly random permutation, adding each vertex with no neighbor already selected.RGMIS(G, π) denotes the output for graph G and permutation π.Source: §2 · p. 4
  • The graph is accessed through adjacency-matrix queries, which report whether a given vertex pair is an edge; adjacency-list queries are also defined.The paper writes |V| = n and |E| = m.Source: §2 · p. 4
  • The paper targets estimating the greedy MIS size, using list-query and matrix-query oracles to test membership of a uniformly random vertex.Their expected running times are O(Δ(G)) and O(n), respectively.Source: §2 · pp. 4–5

3 Estimating |RGMIS(G, π)|

Algorithm 3 estimates the size of the random-order greedy MIS by partially constructing it, then sampling vertices and testing their membership. It returns a (1 + ϵ)-approximation with high probability and has expected running time O(n^1+1/3 log^4 n/ϵ^2).

3 Estimating |RGMIS(G, π)|

  • Algorithm 3 partially runs the greedy process for Θ(n^1+1/3) steps that add a vertex, forming the baseline independent set Sb.If it processes the whole node set, it can return the MIS size exactly.Source: §3 · p. 5
  • With high probability, Algorithm 3 returns a (1 + ϵ)-approximation to |RGMIS(G, π)|.The estimator uses a sample average of membership indicators and a Chernoff bound.Source: §3 · p. 6
  • The query-cost analysis bounds the expected work for a uniform random vertex of U by O(n log^2 n).The expected total is O(n^1+1/3 log^4 n/ϵ^2); a failure event of probability at most 1/n^10 contributes only O(n^-8 log^4 n/ϵ^2).Source: §3 · pp. 7–8
  • The algorithm samples O(n log n/(|Sb| · ϵ^2)) vertices and tests membership, using greedy checks for vertices in Sb ∪ NG(Sb) and OSb otherwise.OSb is the adjacency-matrix oracle restricted to U = V \ (Sb ∪ NG(Sb)).Source: §3 · pp. 5, 8
  • O(n^1+1/3 log^4 n/ϵ^2) is Algorithm 3’s expected running time.The analysis bounds the expected query complexity, which determines running time.Source: §3 · p. 8

4 Query Complexity of OSb

The query-complexity analysis separates OSb’s work on the residual graph from queries involving vertices outside it. It controls the latter through staged checks against the partially built set Sb and a high-probability residual-degree bound.

4 Query Complexity of OSb

  • Within G[U], OSb makes the same matrix queries as OM and the same list queries as OL; expected real-query counts are O(|U|) and O(Δ(G[U])).A real matrix-query has both endpoints in U; a real list-query is an edge with both endpoints in U.Source: §4 · p. 9
  • OSb also makes spurious queries from U to vertices outside U, and the analysis bounds their cost by relating suffix-query counts to induced-subgraph query counts.The expected suffix length is analyzed by conditioning on the induced-subgraph query positions.Source: §4 · pp. 9, 11
  • Conditioned on ΔSb, the residual degree bound holds for each relevant prefix of Sb with probability at least 1 − 1/n^10.The analysis conditions on this event and on the permutation prefix through i0.Source: §4 · p. 9
  • A real list-query costs |Sb| + 1 adjacency queries to verify both that its endpoint is not banned and that the edge exists.A real matrix-query that is not a real list-query requires one adjacency-matrix query.Source: §4 · p. 10
  • O(n log^2 n/|Vi0 \ U|) expected adjacency queries suffice for a U-query between u ∈ U and a random vertex of Vi0 \ U, conditioned on ΔSb.The analysis uses nested residual sets whose maximum degrees decrease as Sb grows.Source: §4 · p. 10

5 Sublinear Metric k-Center via Independent Set

The section reduces general-metric k-center to MIS-size estimation, yielding a sublinear (1 + ϵ, 2 + ϵ) bi-criteria approximation for k ∈ ω(n^1/3).

5 Sublinear Metric k-Center via Independent Set

  • For k ∈ ω(n^1/3), the reduction gives a sublinear (1 + ϵ, 2 + ϵ)-bi-criteria approximation for metric k-center.The guarantee allows up to (1 + ϵ)k centers with radius at most (2 + ϵ) times the k-center optimum.Source: §5 · pp. 14–15
  • In G_r, an MIS of size at most k gives a k-center cover of radius r, while OPT_k ≤ r/2 implies |MIS(G_r)| ≤ k.G_r connects pairs at distance at most r; maximality ensures every point is within r of an MIS point.Source: §5 · pp. 14–15
  • The algorithm sweeps geometrically increasing radii from a pairwise-distance lower bound, estimates MIS size on each threshold graph, and returns the smallest radius meeting its acceptance criterion.It invokes the assumed (1 + ϵ)-approximate MIS-size estimator at each tested radius.Source: §5 · pp. 14–15
  • The radius sweep tests O(log(∆)/ϵ) values, with each test invoking the MIS-size estimator.The metric input consists of points with pairwise-distance queries, and ∆ bounds the ratio of maximum to minimum pairwise distance.Source: §5 · pp. 14–15
Loading 2610.03588v1…