An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination

Kleitos Papadopoulos

arxiv: 2605.20526 · v1 · pith:SCSM7PVYnew · submitted 2026-05-19 · 💻 cs.DS

An O(n⁵)-Time Algorithm for Optimal Broadcast Domination

Kleitos Papadopoulos This is my paper

Pith reviewed 2026-05-21 06:30 UTC · model grok-4.3

classification 💻 cs.DS

keywords broadcast dominationgraph algorithmsdynamic programmingdomination graphpath casetime complexityefficient algorithmO(n^5)

0 comments

The pith

A new O(n^3) path-case algorithm improves optimal broadcast domination to O(n^5) time on general graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to improve the time complexity of computing optimal broadcast domination, where powers are assigned to vertices to cover the graph with minimal total power. It builds on a prior reduction that shows optimal solutions correspond to path or cycle domination graphs. By designing a single directed acyclic graph for states of oriented broadcast balls and residual sides, the path case is solved faster than before. This leads to an overall O(n^5) algorithm when combined with the peel reduction. A reader would care if they need exact solutions for broadcast problems in networks, as the speedup makes larger graphs tractable.

Core claim

The paper establishes an O(n^3)-time and O(n^3)-space algorithm for the path-case subproblem of optimal broadcast domination on an n-vertex graph. The key is building one directed acyclic graph with states as oriented broadcast balls together with their two possible residual sides, rather than one auxiliary graph per left endpoint vertex. When this is used with the peel-one-ball reduction, the general problem on connected unweighted graphs is solved in O(n^5) time.

What carries the argument

Single directed acyclic graph whose states are oriented broadcast balls with their two possible residual sides; it enables dynamic programming to compute minimum cost coverings for the path case efficiently.

Load-bearing premise

Some optimal efficient broadcast has a domination graph that is a path or a cycle.

What would settle it

A connected unweighted graph where the minimum broadcast cost computed by the algorithm differs from the cost found by exhaustive search on all possible power assignments.

Figures

Figures reproduced from arXiv: 2605.20526 by Kleitos Papadopoulos.

**Figure 1.** Figure 1: An oriented state σ = (b, Lσ, Rσ), where b = (cσ, rσ) and Xσ = B(cσ, rσ). The sets Lσ and Rσ are the two oriented residual sides of H[V (H) \ Xσ]. 4 An anchor-free path-case algorithm Let H = (V, E) be a connected graph on s vertices. In this section we compute γpath(H) in O(s 3 ) time. If s = 1, we return the zero broadcast by the convention γpath(K1) = 0. Therefore assume for the remainder of this sectio… view at source ↗

**Figure 2.** Figure 2: A directed arc σ → τ shown through the two relevant residual decompositions. In the σ-decomposition, Xτ lies in the right residual side Rσ and covers the exposed right frontier of σ. In the τ -decomposition, Xσ lies in the left residual side Lτ and covers the exposed left frontier of τ . 4.2 The state digraph We build a weighted directed graph D(H). Its vertices are all states. The weight of a state σ is r… view at source ↗

**Figure 3.** Figure 3: Measured speedup of the anchor-free implementation over the HL-style anchored [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

read the original abstract

Broadcast domination assigns a nonnegative integer power to every vertex of a graph so that every vertex is within the assigned power of some broadcasting vertex, and the objective is to minimize the sum of the powers. Heggernes and Lokshtanov proved that the problem is polynomial-time solvable on arbitrary connected unweighted graphs by showing that some optimal efficient broadcast has a domination graph that is a path or a cycle, and by reducing the general case to an $O(n^6)$-time algorithm. This paper gives an efficient algorithm of the path-case. Instead of building one auxiliary acyclic graph for every possible left endpoint vertex, we build a single directed acyclic graph whose states are oriented broadcast balls together with their two possible residual sides. The resulting path-case algorithm runs in $O(n^3)$ time and $O(n^3)$ space on an $n$-vertex graph. Combining this routine with the same peel-one-ball reduction of Heggernes and Lokshtanov yields an exact $O(n^5)$-time algorithm for optimal broadcast domination on arbitrary connected unweighted graphs. This resolves the quintic-time conjecture for general graphs attributed to Heggernes and S\ae ther and recorded in subsequent surveys of broadcast domination.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper improves the path-case solver for broadcast domination to O(n^3) via a single DAG on oriented balls and residuals, which combines with prior reduction to give O(n^5) overall and resolves the quintic conjecture.

read the letter

The main thing to know is that the authors replace the per-endpoint auxiliary graphs from earlier work with one directed acyclic graph whose nodes are oriented broadcast balls paired with residual sides. This yields an O(n^3)-time path-case algorithm that, when plugged into the existing peel-one-ball reduction, produces an O(n^5) exact algorithm for general connected unweighted graphs and settles the conjecture recorded by Heggernes and Sæther. The construction is the concrete novelty here and looks like a clean way to avoid redundant work across left endpoints while still tracking coverage and cost. The paper does a good job stating how the new device fits the prior structural result about path or cycle domination graphs and clearly flags the complexity gain. The soft spots are limited but real. The abstract gives the state space and high-level idea without the recurrence, transition rules, or full running-time proof, so those details need checking to confirm the cubic bound holds without hidden factors or missed cases in the residual handling. The reliance on the earlier structural theorem is inherited rather than re-proven, which is fine but means any gap there carries over. This is for people working on exact polynomial algorithms for domination and broadcasting problems in graphs. A reader focused on dynamic programming refinements or fine-grained improvements inside P would get direct value from the technique. It deserves a serious referee to verify the DAG correctness and analysis.

Referee Report

1 major / 2 minor

Summary. The manuscript claims an O(n^3)-time algorithm for the path-case subproblem of optimal broadcast domination, obtained by constructing a single directed acyclic graph whose nodes are oriented broadcast balls paired with their two possible residual sides. This is combined with the existing peel-one-ball reduction of Heggernes and Lokshtanov to produce an O(n^5)-time exact algorithm for arbitrary connected unweighted graphs, improving the prior O(n^6) bound and resolving the quintic-time conjecture.

Significance. If the DAG transitions and dynamic-programming analysis are correct, the result is a meaningful improvement in the exact complexity of broadcast domination. The technical contribution of replacing per-endpoint auxiliary graphs with one global DAG is a clear optimization that directly yields the cubic bound for the path case while correctly invoking the structural theorem that some optimal efficient broadcast has a path or cycle domination graph.

major comments (1)

The high-level description of the state space (oriented broadcast balls with residual sides) is given, but no explicit recurrence, transition rules, or running-time analysis for the dynamic program on the DAG appears in the provided text; without these the O(n^3) claim cannot be verified and is load-bearing for the central complexity result.

minor comments (2)

The abstract states that the new routine 'resolves the quintic-time conjecture' but does not cite the specific survey or paper in which the conjecture is recorded; adding this reference would improve context.
Notation for 'residual sides' and 'oriented broadcast balls' should be introduced with a small example or figure before the DAG construction is described.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of the result and for the constructive comment on the exposition of the dynamic program. We address the major comment below and will incorporate the requested details into the revised manuscript.

read point-by-point responses

Referee: The high-level description of the state space (oriented broadcast balls with residual sides) is given, but no explicit recurrence, transition rules, or running-time analysis for the dynamic program on the DAG appears in the provided text; without these the O(n^3) claim cannot be verified and is load-bearing for the central complexity result.

Authors: We agree that the manuscript currently gives only a high-level description of the states (oriented broadcast balls paired with residual sides) without spelling out the recurrence, transitions, or time analysis. In the revision we will add a dedicated subsection that (1) states the recurrence for the minimum cost to reach each DAG node, (2) enumerates the transition rules that extend a ball or flip a residual side while respecting the path ordering, and (3) proves that the DAG has O(n^2) nodes and O(n) outgoing edges per node, yielding an O(n^3)-time DP. This will make the cubic bound for the path case fully verifiable while preserving the overall O(n^5) result obtained by combining the routine with the existing peel-one-ball reduction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation combines external reduction with independent new DAG solver

full rationale

The paper's central result combines the structural theorem and peel-one-ball reduction from Heggernes and Lokshtanov (distinct prior authors) with a novel O(n^3) path-case solver. The new solver is defined directly via a single global DAG whose states are oriented broadcast balls paired with residual sides, with transitions encoding coverage and minimization; this construction does not reduce to any self-citation, fitted parameter, or ansatz from the present authors. The overall O(n^5) claim therefore rests on an externally supported reduction plus an independently specified dynamic program, rendering the derivation self-contained against external benchmarks with no load-bearing circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the path-or-cycle structural theorem from earlier work together with the correctness of the new single-DAG dynamic program; no free parameters or invented entities are introduced.

axioms (1)

domain assumption Some optimal efficient broadcast has a domination graph that is a path or a cycle
Invoked to justify reducing the general problem to repeated path-case instances via the peel-one-ball method

pith-pipeline@v0.9.0 · 5741 in / 1341 out tokens · 50132 ms · 2026-05-21T06:30:35.638299+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Instead of building one auxiliary acyclic graph for every possible left endpoint vertex, we build a single directed acyclic graph whose states are oriented broadcast balls together with their two possible residual sides.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

Heggernes and D

P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time.Dis- crete Mathematics, 306(24):3267–3280, 2006. doi:10.1016/j.disc.2006.06.013

work page doi:10.1016/j.disc.2006.06.013 2006
[2]

D. J. Erwin. Dominating broadcasts in graphs.Bulletin of the Institute of Combinatorics and its Applications, 42:89–105, 2004

work page 2004
[3]

J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi, and S. T. Hedet- niemi. Broadcasts in graphs.Discrete Applied Mathematics, 154(1):59–75, 2006. doi:10.1016/j.dam.2005.07.009

work page doi:10.1016/j.dam.2005.07.009 2006
[4]

J. R. S. Blair, P. Heggernes, S. Horton, and F. Manne. Broadcast domination algorithms for interval graphs, series-parallel graphs, and trees.Congressus Numerantium, 169:55–77, 2004

work page 2004
[5]

Heggernes and S

P. Heggernes and S. H. Sæther. Broadcast domination on block graphs in linear time. InComputer Science – Theory and Applications, CSR 2012, Lecture Notes in Computer Science 7353, pages 172–183. Springer, 2012. doi:10.1007/978-3-642-30642-6 17

work page doi:10.1007/978-3-642-30642-6 2012
[6]

M. A. Henning, G. MacGillivray, and F. Yang. Broadcast domination in graphs. In T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, editors,Structures of Domination in Graphs, Developments in Mathematics 66, pages 15–46. Springer, Cham, 2021. doi:10.1007/978-3- 030-58892-2 2

work page doi:10.1007/978-3- 2021
[7]

Foucaud, B

F. Foucaud, B. Gras, A. Perez, and F. Sikora. On the complexity of broadcast domination and multipacking in digraphs.Algorithmica, 83:2651–2677, 2021. doi:10.1007/s00453-021- 00828-5. 14

work page doi:10.1007/s00453-021- 2021

[1] [1]

Heggernes and D

P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time.Dis- crete Mathematics, 306(24):3267–3280, 2006. doi:10.1016/j.disc.2006.06.013

work page doi:10.1016/j.disc.2006.06.013 2006

[2] [2]

D. J. Erwin. Dominating broadcasts in graphs.Bulletin of the Institute of Combinatorics and its Applications, 42:89–105, 2004

work page 2004

[3] [3]

J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi, and S. T. Hedet- niemi. Broadcasts in graphs.Discrete Applied Mathematics, 154(1):59–75, 2006. doi:10.1016/j.dam.2005.07.009

work page doi:10.1016/j.dam.2005.07.009 2006

[4] [4]

J. R. S. Blair, P. Heggernes, S. Horton, and F. Manne. Broadcast domination algorithms for interval graphs, series-parallel graphs, and trees.Congressus Numerantium, 169:55–77, 2004

work page 2004

[5] [5]

Heggernes and S

P. Heggernes and S. H. Sæther. Broadcast domination on block graphs in linear time. InComputer Science – Theory and Applications, CSR 2012, Lecture Notes in Computer Science 7353, pages 172–183. Springer, 2012. doi:10.1007/978-3-642-30642-6 17

work page doi:10.1007/978-3-642-30642-6 2012

[6] [6]

M. A. Henning, G. MacGillivray, and F. Yang. Broadcast domination in graphs. In T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, editors,Structures of Domination in Graphs, Developments in Mathematics 66, pages 15–46. Springer, Cham, 2021. doi:10.1007/978-3- 030-58892-2 2

work page doi:10.1007/978-3- 2021

[7] [7]

Foucaud, B

F. Foucaud, B. Gras, A. Perez, and F. Sikora. On the complexity of broadcast domination and multipacking in digraphs.Algorithmica, 83:2651–2677, 2021. doi:10.1007/s00453-021- 00828-5. 14

work page doi:10.1007/s00453-021- 2021