On the parameterized complexity of Broadcast Independence and Broadcast Packing

Anthony Perez; Edouard Nemery; Florian Sikora; Joanne Dumont

arxiv: 2605.16001 · v1 · pith:4KMVE3OYnew · submitted 2026-05-15 · 💻 cs.DS · cs.CC· cs.DM

On the parameterized complexity of Broadcast Independence and Broadcast Packing

Joanne Dumont , Edouard Nemery , Anthony Perez , Florian Sikora This is my paper

Pith reviewed 2026-05-19 18:51 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.DM

keywords broadcast independencebroadcast packingparameterized complexitytreewidthfixed-parameter tractabilitydynamic programminggraph algorithmsdomination problems

0 comments

The pith

Broadcast Independence and Broadcast Packing are FPT when parameterized by treewidth plus diameter.

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

The paper aims to determine the parameterized complexity of Broadcast Independence and Broadcast Packing on graphs. These problems involve finding large independent or packing broadcasts where the value is the sum of assigned broadcast radii. A sympathetic reader cares because the results extend tractability from trees to graphs with small treewidth and diameter using dynamic programming. The authors provide FPT algorithms for the combined parameter of treewidth and diameter. They also give corollaries for other parameters and hardness results to complete the complexity picture.

Core claim

Broadcast Independence and Broadcast Packing are fixed-parameter tractable parameterized by treewidth plus diameter via dynamic-programming algorithms over nice tree decompositions. As corollaries, both problems are FPT parameterized by k and treewidth and in XP for treewidth alone. Broadcast Independence is W[1]-hard for pathwidth, weighted versions are W[1]-hard for vertex cover, and there is a constant-factor approximation for Broadcast Independence parameterized by treewidth.

What carries the argument

A family of dynamic-programming algorithms over nice tree decompositions that track broadcast assignments, distances, and eccentricities while ensuring independence or packing constraints.

If this is right

Both problems are FPT parameterized by the solution size k together with treewidth.
Both problems are in XP when parameterized by treewidth alone, extending the known tree algorithm.
Broadcast Independence is W[1]-hard parameterized by pathwidth.
The weighted versions of both problems are W[1]-hard parameterized by vertex cover.
There exists a constant-factor approximation algorithm for Broadcast Independence parameterized by treewidth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The dynamic programming technique could potentially apply to related problems such as other forms of domination or covering with distance constraints.
The emphasis on diameter suggests it is essential for bounding the state space in distance-based graph problems.
These algorithms might be implementable for networks where both treewidth and diameter are small in practice.

Load-bearing premise

The input graph has a computable nice tree decomposition of width equal to its treewidth, and eccentricities of vertices can be precomputed in polynomial time to initialize the dynamic programming states.

What would settle it

A specific graph with small treewidth and small diameter where computing the maximum broadcast independence value requires superpolynomial time in the parameter would falsify the FPT claim.

read the original abstract

A broadcast on a connected graph is a function f that assigns each vertex v an integer f(v) with 0 <= f(v) <= ecc(v) where ecc(v) denotes the eccentricity of v. A vertex u hears a broadcasting vertex v (with f(v)>0) if u is at distance at most f(v) from v. Beyond the classical broadcast domination problem, where every vertex is required to hear at least one vertex, two variants raise intriguing combinatorial and algorithmic questions. In an independent broadcast, no broadcasting vertex hears another broadcasting vertex, while a broadcast packing requires that every vertex hears at most one broadcasting vertex. The corresponding problems Broadcast Independence and Broadcast Packing ask for broadcasts of values at least k under these constraints, where the value is the sum of the broadcast values. We initiate a systematic study of the parameterized complexity of such problems. We prove that Broadcast Independence and Broadcast Packing are FPT parameterized by the treewidth plus the diameter of G, with a family of dynamic-programming algorithms over nice tree decompositions. We obtain as a corollary that both problems are FPT parameterized by k and the treewidth of G and XP for treewidth only. The latter result shows that the known algorithm for trees (Bessy and Rautenbach, DAM 2022) can indeed be extended to bounded treewidth graphs. On the negative side, we show that Broadcast Independence is W[1]-hard parameterized by the pathwidth of G. Note that this result completes the picture for parameter k and treewidth for Broadcast Independence since it is known to be W[1]-hard for k only. We complement these results by showing that a weighted version of both problems, where the input comes with a weight function on the edges, is W[1]-hard parameterized by the vertex cover of G. Finally, we provide a constant-factor approximation algorithm parameterized by treewidth for Broadcast Independence.

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

The paper gives FPT algorithms for Broadcast Independence and Packing by treewidth plus diameter, plus pathwidth hardness, but the DP needs checking on exact distance enforcement.

read the letter

The main takeaway is that these two broadcast problems are FPT parameterized by treewidth plus diameter through dynamic programming on nice tree decompositions, and Broadcast Independence is W[1]-hard by pathwidth alone. This fills out the picture beyond the known tree case. The work is new in delivering the first systematic parameterized analysis of the independence and packing variants. The authors lift the tree algorithm to bounded treewidth graphs and obtain the FPT-by-k-plus-treewidth corollary as a direct consequence. They add a W[1]-hardness result for the weighted versions under vertex cover and a constant-factor approximation for independence under treewidth. These results sit on standard tree-decomposition machinery, which is appropriate here because the diameter keeps broadcast values small and the state space manageable. The abstract states the theorems cleanly and the extension from trees is a natural step. One soft spot is the DP handling of global distance constraints. Assigning values to bag vertices and tracking coverage scalars works for local conditions, but once a broadcaster is forgotten in a subtree the exact distance to another broadcaster in a different subtree is no longer directly available. Triangle-inequality bounds from coverage may accept invalid pairs or reject valid ones. The diameter parameter limits the numeric range, yet the paper must show explicitly whether the states include enough interface distance information to make transitions correct. If that detail is missing or only sketched, it is the part that needs tightening in revision. This paper is for researchers working on parameterized algorithms for domination-style problems on graphs with small treewidth. A reader who wants to see how tree results generalize will find the algorithms and hardness proofs useful. It has enough new content and standard but correctly applied methods to deserve a serious referee rather than a desk reject. I would send it to peer review with a request to verify the DP transitions on distances.

Referee Report

1 major / 2 minor

Summary. The manuscript studies the parameterized complexity of Broadcast Independence and Broadcast Packing. It proves both problems are FPT parameterized by treewidth plus diameter via dynamic-programming algorithms over nice tree decompositions. Corollaries include FPT for k plus treewidth and XP for treewidth alone. Broadcast Independence is shown W[1]-hard for pathwidth, completing the picture with the known W[1]-hardness for k. Weighted versions are W[1]-hard for vertex cover, and a constant-factor approximation parameterized by treewidth is given for Broadcast Independence.

Significance. If the central DP claims hold, the results meaningfully extend the known polynomial-time algorithm on trees to bounded-treewidth graphs and delineate the complexity landscape for these metric broadcast problems. The combination of positive FPT results with matching hardness results for pathwidth and vertex cover is a solid contribution to parameterized graph algorithms.

major comments (1)

[FPT algorithm section] FPT algorithm section: the DP states assign f-values in 0..diameter to bag vertices and propagate max-coverage scalars c(x) = max(f(v)-dist(v,x)). This yields only triangle-inequality upper bounds on distances between broadcasters forgotten in different child subtrees. The transitions therefore cannot reliably enforce the exact global constraints dist(u,v) > f(u) and dist(u,v) > f(v) required for independence and packing; a concrete verification that the state augmentation suffices (or an explicit distance-to-interface table) is needed to support the claimed FPT runtime.

minor comments (2)

The abstract states the main theorems clearly but the technical sections should include explicit DP recurrences or pseudocode rather than high-level descriptions of states and transitions.
Eccentricity precomputation and the assumption that a nice tree decomposition of width tw is given should be stated as a separate preprocessing lemma with its polynomial-time bound.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the single major comment below and will revise the manuscript accordingly to strengthen the presentation of the DP.

read point-by-point responses

Referee: [FPT algorithm section] FPT algorithm section: the DP states assign f-values in 0..diameter to bag vertices and propagate max-coverage scalars c(x) = max(f(v)-dist(v,x)). This yields only triangle-inequality upper bounds on distances between broadcasters forgotten in different child subtrees. The transitions therefore cannot reliably enforce the exact global constraints dist(u,v) > f(u) and dist(u,v) > f(v) required for independence and packing; a concrete verification that the state augmentation suffices (or an explicit distance-to-interface table) is needed to support the claimed FPT runtime.

Authors: We thank the referee for this observation on the DP states. The max-coverage scalars c(x) track the strongest influence from forgotten broadcasters to each bag vertex x. At join nodes the c values from the two children are combined by taking the pointwise maximum, and transitions check whether any c(x) would violate the independence or packing condition relative to an f-value on the bag (e.g., c(x) >= f(x) signals a potential hearing violation). Because any pair of broadcasters whose distance constraint is violated must have a path that passes through some bag vertex, the propagated coverage values detect the violation at the first common interface. We therefore maintain that the augmentation is sufficient for exact enforcement. To address the referee's request directly, the revised manuscript will contain an expanded subsection with a concrete verification of the transition rules, including a small example illustrating how the exact constraints dist(u,v) > f(u) and dist(u,v) > f(v) are preserved. We will also note the possibility of an explicit distance-to-interface table as an alternative formulation. revision: yes

Circularity Check

0 steps flagged

No circularity: FPT claims rest on standard treewidth DP machinery

full rationale

The paper derives FPT membership for Broadcast Independence and Broadcast Packing via dynamic programming on nice tree decompositions parameterized by treewidth plus diameter. This uses established techniques for assigning broadcast values (0 to diameter) to bag vertices and enforcing independence or packing constraints locally during bag transitions. Eccentricity precomputation is stated as polynomial-time and independent of the target result. The corollary extending the Bessy-Rautenbach tree algorithm cites external prior work by different authors. No self-definitional reductions, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems, or ansatz smuggling appear in the derivation chain. The approach is self-contained against external benchmarks of treewidth DP.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on standard definitions of eccentricity, treewidth, and nice tree decompositions from prior literature; no new free parameters or invented entities are introduced.

axioms (2)

standard math Every connected graph has a well-defined eccentricity function ecc(v) for each vertex v.
Invoked in the definition of broadcast functions in the abstract.
standard math Nice tree decompositions exist and can be used for dynamic programming on graphs of bounded treewidth.
Central to the stated FPT algorithm.

pith-pipeline@v0.9.0 · 5886 in / 1223 out tokens · 39348 ms · 2026-05-19T18:51:59.575631+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

[1]

Broadcasts on paths and cycles , journal =

Sabrina Bouchouika and Isma Bouchemakh and. Broadcasts on paths and cycles , journal =. 2020 , url =. doi:10.1016/J.DAM.2020.01.030 , timestamp =

work page doi:10.1016/j.dam.2020.01.030 2020
[2]

Hiroshi Eto and Fengrui Guo and Eiji Miyano , title =. J. Comb. Optim. , volume =. 2014 , url =. doi:10.1007/S10878-012-9594-4 , timestamp =

work page doi:10.1007/s10878-012-9594-4 2014
[3]

arXiv preprint arXiv:2305.03516 , year=

Boundary and Hearing Independent Broadcasts in Graphs and Trees , author=. arXiv preprint arXiv:2305.03516 , year=

work page arXiv
[4]

Journal of Combinatorial Optimization , volume=

Distance-independent set problems for bipartite and chordal graphs , author=. Journal of Combinatorial Optimization , volume=. 2014 , publisher=

work page 2014
[5]

International Workshop on Graph-Theoretic Concepts in Computer Science , pages=

On distance-d independent set and other problems in graphs with “few” minimal separators , author=. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2016 , organization=

work page 2016
[6]

Paschos , authortext =

Ioannis Katsikarelis and Michael Lampis and Vangelis Th. Paschos , authortext =. Structurally parameterized d-scattered set , journal =. 2022 , url =. doi:10.1016/J.DAM.2020.03.052 , timestamp =

work page doi:10.1016/j.dam.2020.03.052 2022
[7]

On the broadcast independence number of locally uniform 2-lobsters , journal =

Messaouda Ahmane and Isma Bouchemakh and. On the broadcast independence number of locally uniform 2-lobsters , journal =. 2024 , url =. doi:10.7151/DMGT.2443 , timestamp =

work page doi:10.7151/dmgt.2443 2024
[8]

On the broadcast independence number of caterpillars , journal =

Messaouda Ahmane and Isma Bouchemakh and. On the broadcast independence number of caterpillars , journal =. 2018 , url =. doi:10.1016/J.DAM.2018.03.017 , timestamp =

work page doi:10.1016/j.dam.2018.03.017 2018
[9]

arXiv preprint arXiv:2406.05825 , year=

Broadcast independence and packing in certain classes of trees , author=. arXiv preprint arXiv:2406.05825 , year=

work page arXiv
[10]

Girth, minimum degree, independence, and broadcast independence

Girth, minimum degree, independence, and broadcast independence , author=. arXiv preprint arXiv:1809.09565 , year=

work page internal anchor Pith review Pith/arXiv arXiv
[11]

Algorithmic aspects of broadcast independence , journal =

St. Algorithmic aspects of broadcast independence , journal =. 2022 , url =. doi:10.1016/J.DAM.2022.03.001 , timestamp =

work page doi:10.1016/j.dam.2022.03.001 2022
[12]

Relating broadcast independence and independence , journal =

St. Relating broadcast independence and independence , journal =. 2019 , url =. doi:10.1016/J.DISC.2019.07.005 , timestamp =

work page doi:10.1016/j.disc.2019.07.005 2019
[13]

AKCE International Journal of Graphs and Combinatorics , volume=

Unsolved algorithmic problems on trees , author=. AKCE International Journal of Graphs and Combinatorics , volume=. 2006 , publisher=

work page 2006
[14]

6 Josep Díaz, Olli Pottonen, Maria J

Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

work page doi:10.1007/978-3-319-21275-3 2015
[15]

Dunbar and David J

Jean E. Dunbar and David J. Erwin and Teresa W. Haynes and Sandra Mitchell Hedetniemi and Stephen T. Hedetniemi , title =. Discret. Appl. Math. , volume =. 2006 , url =. doi:10.1016/J.DAM.2005.07.009 , timestamp =

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

Heule, Marijn J. H. and Szeider, Stefan , year=. A SAT Approach to Clique-Width , ISBN=. doi:10.1007/978-3-642-39071-5_24 , booktitle=

work page doi:10.1007/978-3-642-39071-5_24
[17]

2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=

Solving connectivity problems parameterized by treewidth in single exponential time , author=. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=. 2011 , organization=

work page 2011
[18]

The Graph Parameter Hierarchy , author=

work page
[19]

Krzysztof Pietrzak , title =. J. Comput. Syst. Sci. , volume =. 2003 , url =. doi:10.1016/S0022-0000(03)00078-3 , timestamp =

work page doi:10.1016/s0022-0000(03)00078-3 2003
[20]

2025 , note =

Broadcast Independence and Broadcast Packing , author=. 2025 , note =

work page 2025
[21]

2001 , publisher=

Cost domination in graphs , author=. 2001 , publisher=

work page 2001
[22]

Reducibility among combinatorial problems

Karp, Richard M. Reducibility among Combinatorial Problems. Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations. 1972. doi:10.1007/978-1-4684-2001-2_9

work page doi:10.1007/978-1-4684-2001-2_9 1972
[23]

Discrete Mathematics , volume=

Optimal broadcast domination in polynomial time , author=. Discrete Mathematics , volume=. 2006 , publisher=

work page 2006
[24]

Neˇ setˇ ril and P

Jaroslav Nesetril and Patrice Ossona de Mendez , title =. 2012 , url =. doi:10.1007/978-3-642-27875-4 , isbn =

work page doi:10.1007/978-3-642-27875-4 2012

[1] [1]

Broadcasts on paths and cycles , journal =

Sabrina Bouchouika and Isma Bouchemakh and. Broadcasts on paths and cycles , journal =. 2020 , url =. doi:10.1016/J.DAM.2020.01.030 , timestamp =

work page doi:10.1016/j.dam.2020.01.030 2020

[2] [2]

Hiroshi Eto and Fengrui Guo and Eiji Miyano , title =. J. Comb. Optim. , volume =. 2014 , url =. doi:10.1007/S10878-012-9594-4 , timestamp =

work page doi:10.1007/s10878-012-9594-4 2014

[3] [3]

arXiv preprint arXiv:2305.03516 , year=

Boundary and Hearing Independent Broadcasts in Graphs and Trees , author=. arXiv preprint arXiv:2305.03516 , year=

work page arXiv

[4] [4]

Journal of Combinatorial Optimization , volume=

Distance-independent set problems for bipartite and chordal graphs , author=. Journal of Combinatorial Optimization , volume=. 2014 , publisher=

work page 2014

[5] [5]

International Workshop on Graph-Theoretic Concepts in Computer Science , pages=

On distance-d independent set and other problems in graphs with “few” minimal separators , author=. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2016 , organization=

work page 2016

[6] [6]

Paschos , authortext =

Ioannis Katsikarelis and Michael Lampis and Vangelis Th. Paschos , authortext =. Structurally parameterized d-scattered set , journal =. 2022 , url =. doi:10.1016/J.DAM.2020.03.052 , timestamp =

work page doi:10.1016/j.dam.2020.03.052 2022

[7] [7]

On the broadcast independence number of locally uniform 2-lobsters , journal =

Messaouda Ahmane and Isma Bouchemakh and. On the broadcast independence number of locally uniform 2-lobsters , journal =. 2024 , url =. doi:10.7151/DMGT.2443 , timestamp =

work page doi:10.7151/dmgt.2443 2024

[8] [8]

On the broadcast independence number of caterpillars , journal =

Messaouda Ahmane and Isma Bouchemakh and. On the broadcast independence number of caterpillars , journal =. 2018 , url =. doi:10.1016/J.DAM.2018.03.017 , timestamp =

work page doi:10.1016/j.dam.2018.03.017 2018

[9] [9]

arXiv preprint arXiv:2406.05825 , year=

Broadcast independence and packing in certain classes of trees , author=. arXiv preprint arXiv:2406.05825 , year=

work page arXiv

[10] [10]

Girth, minimum degree, independence, and broadcast independence

Girth, minimum degree, independence, and broadcast independence , author=. arXiv preprint arXiv:1809.09565 , year=

work page internal anchor Pith review Pith/arXiv arXiv

[11] [11]

Algorithmic aspects of broadcast independence , journal =

St. Algorithmic aspects of broadcast independence , journal =. 2022 , url =. doi:10.1016/J.DAM.2022.03.001 , timestamp =

work page doi:10.1016/j.dam.2022.03.001 2022

[12] [12]

Relating broadcast independence and independence , journal =

St. Relating broadcast independence and independence , journal =. 2019 , url =. doi:10.1016/J.DISC.2019.07.005 , timestamp =

work page doi:10.1016/j.disc.2019.07.005 2019

[13] [13]

AKCE International Journal of Graphs and Combinatorics , volume=

Unsolved algorithmic problems on trees , author=. AKCE International Journal of Graphs and Combinatorics , volume=. 2006 , publisher=

work page 2006

[14] [14]

6 Josep Díaz, Olli Pottonen, Maria J

Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

work page doi:10.1007/978-3-319-21275-3 2015

[15] [15]

Dunbar and David J

Jean E. Dunbar and David J. Erwin and Teresa W. Haynes and Sandra Mitchell Hedetniemi and Stephen T. Hedetniemi , title =. Discret. Appl. Math. , volume =. 2006 , url =. doi:10.1016/J.DAM.2005.07.009 , timestamp =

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

[16] [16]

Heule, Marijn J. H. and Szeider, Stefan , year=. A SAT Approach to Clique-Width , ISBN=. doi:10.1007/978-3-642-39071-5_24 , booktitle=

work page doi:10.1007/978-3-642-39071-5_24

[17] [17]

2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=

Solving connectivity problems parameterized by treewidth in single exponential time , author=. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=. 2011 , organization=

work page 2011

[18] [18]

The Graph Parameter Hierarchy , author=

work page

[19] [19]

Krzysztof Pietrzak , title =. J. Comput. Syst. Sci. , volume =. 2003 , url =. doi:10.1016/S0022-0000(03)00078-3 , timestamp =

work page doi:10.1016/s0022-0000(03)00078-3 2003

[20] [20]

2025 , note =

Broadcast Independence and Broadcast Packing , author=. 2025 , note =

work page 2025

[21] [21]

2001 , publisher=

Cost domination in graphs , author=. 2001 , publisher=

work page 2001

[22] [22]

Reducibility among combinatorial problems

Karp, Richard M. Reducibility among Combinatorial Problems. Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations. 1972. doi:10.1007/978-1-4684-2001-2_9

work page doi:10.1007/978-1-4684-2001-2_9 1972

[23] [23]

Discrete Mathematics , volume=

Optimal broadcast domination in polynomial time , author=. Discrete Mathematics , volume=. 2006 , publisher=

work page 2006

[24] [24]

Neˇ setˇ ril and P

Jaroslav Nesetril and Patrice Ossona de Mendez , title =. 2012 , url =. doi:10.1007/978-3-642-27875-4 , isbn =

work page doi:10.1007/978-3-642-27875-4 2012