Theorem A — constant-round -approximate fractional covers for general covering relations on
OpenShortBroadcastDom.Supplement.theorem_AFix rationals and and an integer . There is a deterministic broadcast CONGEST algorithm with a constant number of rounds (depending only on ) with the following guarantee. Let , let be the demands, let every demand have a nonempty covering set , and let the costs satisfy ; every vertex knows only its identifier, its demand bit, its cost and the incidence information of the covering relation. Then the algorithm outputs a vector , supported on the vertices that belong to some covering set, with
Identifiers are distinct with bits, messages have bits, and the algorithm needs no auxiliary graph structure, degree bound or knowledge of .
This is the fractional solver of the paper in its general form: it covers open neighbourhoods (total domination), partial domination, forbidden candidates and red-blue domination.
Formalization Note One algorithm and one round count are chosen before the identifier exponent and the graph; only the message constant depends on . The output is a rational per vertex.
Differences from the source:
- reading: broadcast CONGEST (each vertex receives its neighbours' messages) → the multiset of the neighbours' messages, without port numbers; reason: gives the algorithm less information, so the existence statement is at least as strong; a sender can prepend its O(log(n+1))-bit identifier
- reading: constant-round, identifiers and messages of O(log(n+1)) bits → ∃ algorithm ∃ T, ∀ k ∃ c: identifiers < (n+1)^k, messages ≤ c(⌊log₂ n⌋+1) bits; reason: the algorithm and its round count are independent of the identifier constant k; this is the stronger quantifier order
- encoding: for each edge rv both ends know whether v ∈ C(r); each demand knows whether r ∈ C(r); every vertex knows its demand bit and cost → local input covInput: demand bit, cost, self-cover bit, identifier sets of the incident covering pairs; reason: the broadcast model has no ports; identifiers of neighbours are learnable in one round, so no information is added
- encoding: costs c_v ∈ {1,…,b} for the candidates (admissible vertices) → costs in {1,…,b} at every vertex; reason: a vertex in no covering set covers nothing and its cost does not enter τ_c; the output is zero there, so the instances correspond one to one
- reading: a feasible fractional cover → x ≥ 0, x_v = 0 at every vertex in no C(r), and ∑_{v∈C(r)} x_v ≥ 1 for every demand; reason: §6.6 (p.42) says the output is a feasible vector on the admissible vertices; requiring it is at least as strong
import Mathlib import Definitions.Def_ShortBroadcastDom_closedNbhd import Definitions.Def_ShortBroadcastDom_InClassC import Definitions.Def_ShortBroadcastDom_BroadcastAlg import Definitions.Def_ShortBroadcastDom_Supplement_tauRel import Definitions.Def_ShortBroadcastDom_Supplement_covInput
namespace ShortBroadcastDom.Supplement
open ShortBroadcastDom
/-- **Theorem A (constant-round fractional solver for general covering relations).** Amiri,
Siebertz, Wawrzyniak, *Paying for Fractional Error* (arXiv:2611.02057, sha256 prefix f4dc98d2),
§1.1, p.2 (PDF 5): "For fixed rationals ρ ≥ 1 and δ > 0, and a fixed integer b ≥ 1, there is an
algorithm that computes a feasible fractional cover of cost at most (1 + δ)τc on every G ∈ Cρ in a
constant number of deterministic broadcast CONGEST rounds. The algorithm requires no auxiliary
graph structure, degree bound, or knowledge of the graph order." Setting (p.2): each demand `r` has
a nonempty set `C(r) ⊆ N[r]` of allowed candidates and the costs lie in `{1, …, b}`. Proved in
§6.6, pp.40–42.
**Formalization Note** For the fixed parameters there is one algorithm `alg` and one round count
`T`, chosen before the identifier exponent `k` and the graph; only the message constant `c` depends
on `k`. The local input is `covInput` (demand bit, cost, the incidence information of p.2) and the
output a rational `x_v`. The output is a feasible fractional cover: `x ≥ 0`, `x_v = 0` at every
vertex in no covering set (a vector on the admissible vertices, §6.6, p.41), and
`∑_{v ∈ C(r)} x_v ≥ 1` for every demand. Costs are given at every vertex; the cost of a vertex in no
covering set is irrelevant. -/
theorem theorem_A (ρ δ : ℚ) (hρ : 1 ≤ ρ) (hδ : 0 < δ) (b : ℕ) (hb : 1 ≤ b) :
∃ alg : BroadcastAlg CovInput ℚ, ∃ T : ℕ, ∀ k : ℕ, ∃ c : ℕ,
∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(id : V → ℕ) (R : Finset V) (Cov : V → Finset V) (cost : V → ℕ),
ValidIds k (Fintype.card V) id → InClassC (ρ : ℝ) G →
(∀ r ∈ R, (Cov r).Nonempty ∧ Cov r ⊆ closedNbhd G r) →
(∀ v, 1 ≤ cost v ∧ cost v ≤ b) →
MsgBounded alg G id (covInput G id R Cov cost) T c (Fintype.card V) ∧
(∀ v, 0 ≤ alg.realOut G id (covInput G id R Cov cost) T v) ∧
(∀ v, (∀ r ∈ R, v ∉ Cov r) → alg.realOut G id (covInput G id R Cov cost) T v = 0) ∧
(∀ r ∈ R, 1 ≤ ∑ v ∈ Cov r, alg.realOut G id (covInput G id R Cov cost) T v) ∧
∑ v, (cost v : ℝ) * alg.realOut G id (covInput G id R Cov cost) T v ≤
(1 + (δ : ℝ)) * tauRel R Cov (fun v => (cost v : ℝ)) := by sorry
end ShortBroadcastDom.Supplement