Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algorithm D stops within log(n²)/log(18/17) + 16 ≤ 25·log n + 16 rounds with a maximal independent set

Proved
LubyMIS.Derandomized.algorithmD_rounds

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

derandomizationgraph-algorithmsmaximal-independent-setp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let GGG be a graph on the vertices {0,…,n−1}\{0, \dots, n-1\}{0,…,n−1} and let qqq be a prime with n≤q≤2nn \le q \le 2nn≤q≤2n. Every run of Algorithm D terminates: there is a kkk such that the vertex set V′V'V′ of the current graph is nonempty before each of the first kkk executions of the loop body and empty after the kkk-th, so the loop body is executed exactly kkk times. Moreover

k ≤ log⁡(n2)log⁡(18/17)+16 ≤ 25⋅log⁡2n+16,k \ \le\ \frac{\log(n^2)}{\log(18/17)} + 16 \ \le\ 25 \cdot \log_2 n + 16,k ≤ log(18/17)log(n2)​+16 ≤ 25⋅log2​n+16,

and the output set III is a maximal independent set of GGG.

This is the deterministic guarantee of Algorithm D: a maximal independent set is found in O(log⁡n)O(\log n)O(logn) parallel rounds without random bits, for every choice of maximizing vertex in Case 1 and every choice of maximizing sample point in Case 2.

Formalization Note The ratio log⁡(n2)/log⁡(18/17)\log(n^2)/\log(18/17)log(n2)/log(18/17) does not depend on the base of the logarithm; 25log⁡n25 \log n25logn is base 2, following the paper's convention that all logarithms are base 2. The statement holds for every run, that is, for every tie-break among vertices of maximum degree and every maximizing sample point. The P-RAM processor count and running time are not part of the statement. For n=0n = 0n=0 no prime q≤0q \le 0q≤0 exists and the statement is vacuous; for n=1n = 1n=1 the bound is 161616.

Preamble
import Mathlib
import Definitions.Def_LubyMIS_Derandomized_Basic
import Definitions.Def_LubyMIS_Derandomized_AlgorithmD
Formal statement
namespace LubyMIS.Derandomized

/-- Algorithm D (Luby 1986, §4.4, p. 1047, with §3.1, p. 1039): for every graph `G` on `n` vertices
and every prime `n ≤ q ≤ 2n`, every run of Algorithm D stops after `k` executions of the loop body
with `k ≤ log(n²)/log(18/17) + 16 ≤ 25·log₂ n + 16`, and the set `I` it outputs is a maximal
independent set of `G`. -/
theorem algorithmD_rounds (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (q : ℕ)
    (hq : q.Prime) (hnq : n ≤ q) (hq2 : q ≤ 2 * n) (s : ℕ → Finset (Fin n) × Finset (Fin n))
    (hs : IsRun G q s) :
    ∃ k : ℕ, (s k).2 = ∅ ∧ (∀ j < k, (s j).2.Nonempty) ∧
      (k : ℝ) ≤ Real.log ((n : ℝ) ^ 2) / Real.log (18 / 17) + 16 ∧
      (k : ℝ) ≤ 25 * Real.logb 2 (n : ℝ) + 16 ∧
      Maximal G.IsIndepSet ((s k).1 : Set (Fin n)) := by sorry

end LubyMIS.Derandomized
Source
Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM J. Comput. 15(4), 1986, p. 1047, §4.4, display on Algorithm D; p. 1039, §3.1 ("I is a maximal independent set in G at the termination of the algorithm")
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Throughout, nnn is a natural number and GGG is a simple graph (undirected, no loops, no multiple edges) on the vertex set Vn={0,1,…,n−1}V_n = \{0, 1, \dots, n-1\}Vn​={0,1,…,n−1}. GGG's adjacency relation is assumed decidable. This is a computability requirement only and places no mathematical restriction on GGG. The statement also takes:

  • a natural number qqq;
  • a sequence s:N→Pfin(Vn)×Pfin(Vn)s : \mathbb{N} \to \mathcal{P}_{\mathrm{fin}}(V_n) \times \mathcal{P}_{\mathrm{fin}}(V_n)s:N→Pfin​(Vn​)×Pfin​(Vn​). For each index jjj, sj=(Ij,Wj)s_j = (I_j, W_j)sj​=(Ij​,Wj​) is a pair of finite subsets of VnV_nVn​. Below, IjI_jIj​ is called the first component and WjW_jWj​ the second component.

Hypotheses.

  1. qqq is prime.
  2. n≤qn \le qn≤q.
  3. q≤2nq \le 2nq≤2n.
  4. IsRun(G,q,s)\mathrm{IsRun}(G, q, s)IsRun(G,q,s) holds. This is a predicate on the graph, the number qqq and the whole sequence sss. It is defined in an imported file whose code is not part of this declaration, so this read-back cannot say what it requires. In particular, it cannot say how sj+1s_{j+1}sj+1​ is related to sjs_jsj​, what s0s_0s0​ is, or whether the predicate can be satisfied at all. Every claim below holds only for sequences that satisfy it.

Conclusion. There exists a natural number kkk with all of the following properties:

  • The second component is empty at step kkk: Wk=∅W_k = \varnothingWk​=∅.
  • kkk is the first such index: Wj≠∅W_j \neq \varnothingWj​=∅ for every j<kj < kj<k.
  • First bound on kkk (natural logarithm):
k  ≤  ln⁡(n2)ln⁡(18/17)+16.k \;\le\; \frac{\ln(n^2)}{\ln(18/17)} + 16.k≤ln(18/17)ln(n2)​+16.
  • Second bound on kkk (base-2 logarithm):
k  ≤  25 log⁡2n+16.k \;\le\; 25\,\log_2 n + 16.k≤25log2​n+16.

The two bounds are asserted separately; neither is derived from the other within the statement.

  • Maximal independent set: the first component IkI_kIk​ is a maximal independent set of GGG. That is:

    • no two distinct vertices of IkI_kIk​ are adjacent in GGG; and
    • every independent set J⊆VnJ \subseteq V_nJ⊆Vn​ with Ik⊆JI_k \subseteq JIk​⊆J satisfies J⊆IkJ \subseteq I_kJ⊆Ik​.

    "Maximal" here means maximal with respect to inclusion, not of maximum size.

The statement says nothing about sjs_jsj​ for j>kj > kj>k. It also says nothing about IjI_jIj​ for j<kj < kj<k beyond what IsRun\mathrm{IsRun}IsRun may impose.

Degenerate cases.

  • n=0n = 0n=0: hypotheses 2 and 3 force q=0q = 0q=0, which is not prime. The hypotheses cannot all hold, so the statement is vacuously true and asserts nothing.
  • n=1n = 1n=1: the hypotheses force q=2q = 2q=2. Both bounds become k≤16k \le 16k≤16, because ln⁡(1)=0\ln(1) = 0ln(1)=0 and log⁡21=0\log_2 1 = 0log2​1=0. The only maximal independent set of the one-vertex loopless graph is {0}\{0\}{0}, so the conclusion requires Ik={0}I_k = \{0\}Ik​={0}.
  • n≥1n \ge 1n≥1 in general: n2≥1n^2 \ge 1n2≥1 and n≥1n \ge 1n≥1, so neither logarithm is evaluated at 000 or at a negative number. The denominator ln⁡(18/17)\ln(18/17)ln(18/17) is a fixed positive number. No default values of total functions arise in the bounds.
  • Whether the statement says anything at all: a prime qqq with n≤q≤2nn \le q \le 2nn≤q≤2n exists for every n≥1n \ge 1n≥1. So whether the theorem has any non-vacuous instance depends entirely on whether IsRun(G,q,s)\mathrm{IsRun}(G, q, s)IsRun(G,q,s) can be satisfied, and that cannot be determined from the code shown.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me