Lemma 6.3 — partition nonnegative integers into three half-bounded classes
ProvedTreewidthApprox.Partition.lemma_6_3balanced-partitioncombinatoricsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonnegative integers with total , and suppose each . Then their indices can be partitioned into three classes such that
This observation groups the weights of graph components into the three parts required by Lemma 2.9.
Formalization Note The classes may be empty, including when . Partitioning indices distinguishes equal-valued integers. The half bounds are expressed as and over natural numbers.
Preamble
import Mathlib
Formal statement
namespace TreewidthApprox.Partition
/-- Lemma 6.3, p. 363: items of size at most half of their total can be
partitioned into three classes, each of size at most half of the total. -/
theorem lemma_6_3 (p : ℕ) (a : Fin p → ℕ) (q : ℕ)
(hq : ∑ i, a i = q) (ha : ∀ i, 2 * a i ≤ q) :
∃ c : Fin p → Fin 3,
∀ j : Fin 3, 2 * ∑ i ∈ Finset.univ.filter (fun i => c i = j), a i ≤ q := by sorry
end TreewidthApprox.Partition
Source
Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk, A c^k n 5-approximation algorithm for treewidth, SIAM J. Comput. 45(2) (2016), p. 363, Lemma 6.3, https://doi.org/10.1137/130947374
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.