We study a recently introduced generalization of distance domination in graphs known as (, )Broadcast Domination: A set of broadcasting vertices transmit a signal of initial strength ; the strength of the signal decays linearly along edges according to distance, that is, a vertex at a distance < from a broadcasting vertex ∈ receives a signal of strength − , for each ∈ . The goal is to determine a set of broadcasting vertices of minimum size, which ensures that every vertex in the network receives a cumulative signal strength of at least . In this paper, we initiate the study of the (, )-Broadcast Domination problem in general graphs. Our results include a general approximation algorithm and optimal polynomial time algorithms for cographs. Moreover, we consider graphs of bounded Neighborhood diversity (nd), and graphs of bounded Iterated type partition number (itp) and give: (i) a fixe d parameter tractable (FPT) algorithm for (, )Broadcast Domination parameterized by nd; (ii) a FPT algorithm for (, )-Broadcast Domination parameterized by itp plus the solution size = ||; (iii) a FPT algorithm for (, )-Broadcast Domination parameterized by itp plus the demand .
that is a distance- dominating set of if any vertex in can be reached by a path of length at most starting from a vertex in . The distance- domination number of a graph is the smallest cardinality of such a set. Notably, distance- domination generalizes standard domination, where distance-1 domination is equivalent to classical domination.
A recent variation of distance domination is the (, )-Broadcast Domination, first defined
by Blessing et al. in [
Another application addresses the issue of efectively crafting accurate and evidence-based
information to combat misinformation. In epidemiology, graph-based information difusion
algorithms can be used to find the smallest set of individuals who can cooperate in immunizing
the vertices in order to prevent the spreading of negative narratives [
Since its introduction, the (, )-Broadcast Domination problem has been extensively
studied in various special classes of graphs: Two-dimensional grids, paths, triangular grids,
matchstick graphs, and -dimensional grids [
Our results include: (i) a general approximation algorithm and (ii) an optimal polynomial time
algorithm for cographs. Moreover, we consider graphs of bounded Neighborhood diversity (nd),
and graphs of bounded Iterated type partition number (itp) and give: (iii) a fixed parameter
tractable (FPT) algorithm for (, )-Broadcast Domination parameterized by nd; (iv) a FPT
algorithm for (, )-Broadcast Domination parameterized by itp plus the solution size =
||; (v) a FPT algorithm for (, )-Broadcast Domination parameterized by itp plus .
We recall that a problem with input size and parameter is called fixed-parameter tractable
(FPT) if it can be solved in time () · , where is a computable function only depending on
and is a constant [
Let = ( (), ()) be an undirected graph and two vertices , ∈ (), we denote by = | ()| the number of vertices in and by (, ) the distance between and in . Moreover, for a vertex ∈ (), we denote by () = { ∈ () | (, ) ∈ ()} the neighborhood of and [] = () ∪ {}. Furthermore, we denote by ,() = { ∈ () | (, ) ≤ } the neighborhood of radius around . Clearly, ,1() = []. In the above notations, we will omit the subscript whenever the graph is clear from the context.
A Dominating set in a graph = (, ) is a subset of such that every vertex not in the set has at least one neighbor in the set. vertices ⊆ is a (, )- Broadcast Dominating set of if for each ∈ , it holds
Given an undirected graph = (, ) and integers ≥
1, a subset of ∑︁ ∈∩()
( − (, )) ≥ , In this paper, we will consider the following problem.
(, )-Broadcast Domination: Input: An undirected graph = (, ) and two integers ≥ Output: Find a (, )-Broadcast Dominating set of minimum size. 2, ≥ 1 We assume that for each ∈ we have ≤ ∑︀ ∈()( − (, )), otherwise, the problem does not admit any solution. This assumption is harmless, in the sense that it is a polynomially verifiable condition that does not impact the results.
It is worth observing that when = 2 and = 1 the (, )-Broadcast Domination problem corresponds to the classical Dominating set problem.
Finally, since the problem can be solved independently in each connected component of the input graph, from now on, we assume that the input graph is connected.
Knowing that (, )-Broadcast Domination generalizes the Dominating set problem, by the
hardness results in [
Theorem 1. (, )-Broadcast Domination cannot be approximated to within a factor of (1 − ) ln in polynomial time for any constant > 0 unless ⊆ ((log log )).
Moreover, using the same arguments of the proof of Theorem 1 in [
→ N given in (2), satisfies the following properties: ( ) if and only if is (, )-Broadcast Dominating set; (v) is submodular. (i) is integer valued; (ii) (∅) = 0; (iii) is non-decreasing; (iv) A set ⊆ satisfies () = () = ( ) is achieved.
Hence, one can apply the natural greedy algorithm, call it , which starts with = ∅ and iteratively adds to the element ∈ ∖ s.t. ( ∪ {}) − () is maximum, until Theorem 2. (, )-Broadcast Domination problem can be approximated in polynomial time by a factor ln + ln(min(, )) + 1.
Wosley [
For a graph = (, ) and integers ≥ 2, ≥ 1, we define a function : 2 → N, as () = ∑︁ (), where () = min , ∈ ︂(
∑︁ ∈∩() ( − (, )) .
︂) ({}) = ∑︁ min ,
︂( ∈
∑︁ ∈{}∩() (− (, )) ︂) =
∑︁
∈()
Proof. By a classical result of Wolsey [
It is worth observing that we can always assume that ≤ − 1, since the distances between two nodes are at most equal to − 1. Hence, the approximation guaranteed by the Theorem is
Cographs have been discovered independently many times since the 1970s, with diferent
equivalent definitions [
A cograph is a graph that can be constructed using the following recursive rules: • Any single-vertex graph is a cograph; • The disjoint union 1 ⊕ 2 of two cographs is a cograph. • The join 1 ⊗ 2 of two cographs is a cograph.
1 ⊕ 2 is the graph with vertex set (1) ∪ (2) and edge set (1) ∪ (2). (1), ∈ (2)}. 1 ⊗
2 has vertex set (1) ∪ (2) and edge set (1) ∪ (2) ∪ {(, ) | ∈
A cotree () is a binary parse tree defining a cograph , in which the leaves are the vertices of and each internal vertex labeled ⊕ (resp. ⊗ ) represents the disjoint union (resp. Observation 1. If a cograph is connected, then the root of the cotree is labeled ⊗ and the Consider a connected cograph = (, ), the cotree associated to , and integers 1. We recursively compute a solution of the (, )-Broadcast Domination problem. The algorithm uses the dynamic-programming design pattern and traverses the cotree in a join) operation. diameter is at most 2. ≥ optimal solutions, for each internal node of ∈ considering all the possible contributions, of vertices in ∖ (). Specifically, we compute bottom-up the solutions associated with each internal node ∈ for each demand ′ = 1, . . . , . A solution with demand ′ = − will be used when we assume that each node in () receives a cumulative signal strength from vertices in ∖ ().
The following definition introduces the values that will be computed by the algorithm in order to be able to compute the solution of the (, )-Broadcast Domination problem.
Given a cograph = (, ) and two integers ≥ 2, ≥ 1 we denote by (, ) the size of a smallest (, )-Broadcast Dominating set for , where the distance function is redefined as ′(, ) = min(2, (, )), for each , ∈ .
For = 0, we also define this value for any cograph as (, 0) = 0.
Formally, we are going to compute the value ((), ′), for each ∈ and ′ = 0, 1, . . . , . components of () is 2 in .
Observation 2. The reason for using the redefined distance function is as follows. For each internal node ∈ labeled with ⊗ (join) the redefined function matches the original one, while when is labeled with ⊕ (disjoint union), we have that is associated with two disconnected components. In this case, since the graph is connected, and the vertices in (), by construction, will share the same neighborhood in ∖ (), we know that the distance between vertices belonging to diferent is ((), ) where is the root of .
The solution for the instance ⟨, , ⟩ of our original (, )-Broadcast Domination problem recursively in time (2).
Lemma 2. For each ∈ , the computation of ((), ′) for each ′ = 1, . . . , can be done values of ((), ′), for each ′ = 1, . . . , .
Proof. Consider a node ∈ , we show how to use a bottom-up strategy to compute all the For each leaf ∈ we have that () is a single vertex. Then, nodes, we show how to calculate each value ((), ′), for each ′ = 1, . . . , , in time (′).
We have two cases to consider according to the label of (cf. Definition 3): 1) Node is labeled ⊕ (i.e., represents the disjoint union operation).
In this case we have that () = 1 ⊕ 2 where 1 = (1, 1) and 2 = (2, 2) are the graphs associated with the children of in . By Observation 2, we assume that the distance between vertices belonging to the two components 1 and 2 is 2.
For each ′ = 1, . . . , , we can fix the demand 1 (2) for 1 (2) and compute the solution for the other graph 2 (1) ensuring that both solutions satisfy the demand ′.
Fixed the value of ′, we denote by 1 the minimum value of 1, which represents the portion of the demand ′ satisfied by vertices in 1. Since the distance between vertices belonging to the two components is 2, we have that each vertex in 2 provides a signal strength of − vertices in 1 and overall they should cover the residual demand ′ − 1. Hence, the value of 1 2 to corresponds to the smallest non negative integer such that |2| ≥ which corresponds to the residual demand on 1. We have, a value of 1 smaller than 1, we have that the contribution of vertices in 2 is not enough to reach ′ and hence such values are not compatible with a solution for (). Then, for each 1 ≤ 1 ≤ ′, we compute the value 2 = max(0, ′ − (− 2) (1, 1)), which corresponds to the residual demand on 2. Similarly, let 2 the smallest non negative integer such that |1| ≥ ⌈︁ ′− 2 ⌉︁. For each 2 ≤ 2 ≤ ′, we compute the value 1 = max(0, ′ − ( − 2) (2, 2)), − 2 − 2 ⌈︁ ′− 1 ⌉︁. Indeed, by choosing (3) min ︂(
min
min 2≤ 2≤ ′ ︂( ︂( (2, 2)+ max distance between vertices belonging to the two components 1 and 2 is 1. Let () = 1 ⊗ 2) Node is labeled ⊗ (i.e., represents the join operation).
2. We repeat the reasoning above by considering that, in this case,the
Let 1 be the smallest non negative integer such that |2| ≥ ′, we compute the value 2 = max(0, ′ − ( − 1) (1, 1)).
Similarly, let 2 the smallest non negative integer such that |1| ≥ 2 ≤ 2 ≤ ′, we compute the value 1 = max(0, ′ − ( − 1) (2, 2)). We have, − 1 ⌈︁ ′− 2 ⌉︁. For each ⌈︁ ′− 1 ⌉︁. For each 1 ≤ 1 ≤ − 1 min
min
min algorithm is correct and the overall computation associated to a node ∈ is (2). with the definition of (· , · ) and both the values are computed in time (′); hence, the Theorem 3. When is a cograph, the (, )-Broadcast Domination problem is solvable in time (2 + ).
Proof. We recall that: (i) Building the cotree associated to a given cograph can be done in linear time (( + )); (ii) the cotree contains 2 − 1 vertices (it has leaves). Hence, exploiting Lemma 2, we can build the desired solution (, ) in time (2 + ). The optimal set can be computed in the same time by standard backtracking techniques. 5. Graphs of bounded neighborhood diversity or itp number In this section, we recall the definitions of Neighborhood diversity and Iterated type partition number of a graph and give FPT algorithms for graphs in which such parameters are bounded. Definition 5. The following operations can be used to construct any graph: (O1) The creation of an isolated vertex. (O2) The substitution of the vertices 1, . . . , ℓ of an outline graph by the graphs 1, . . . , ℓ, denoted by (1, . . . , ℓ), is the graph = (, ) with = ⋃︀ = 1≤ ≤ ℓ 1≤ ≤ ℓ () ⋃︁ ()∪{(, ) | ∈ , ∈ , (, ) ∈ (), 1 ≤ < ≤ ℓ}.
Notice that the disjoint union and join operations of Definition 2 are special cases of (O2) with ℓ = 2. vertices in , that is, = ⋃︀
1≤ ≤ ℓ where ⊆ (). () = () ∖ (), for each = 1, . . . , ℓ.
Let = (1, . . . , ℓ) be a connected graph. According to operation (O2): is a connected outline graph with ℓ vertices and is a subgraph of such that for all , ∈ (), () ∖
Let be a (, )-Broadcast Dominating set of . Denote by the subset of including the ∈ (), we have
In the following, we give a reformulation of the condition in (1) of Definition 1 that takes into account the construction of in terms of the operation (O1)–(O2) described in Definition 5 and that will be useful to present our algorithms.
Since is a connected graph then also is a connected graph. Hence, we have that (, ) = (, ) for each ∈ ( ) for ̸= . Hence, knowing that ≥ each vertex ∈ (), with 1 ≤ ≤ ℓ, is at distance at most 2 from any ∈ (), and 2, for each | ∩ ,()| = | ∩ ()| +
| ∩ ( )| = || + ∑︁ |̸= (,)≤ and
∑︁ (, ) = ∑︁ (, ) + ∈ ∑︁ |̸= (,)≤ | | (, ) (( − 2) || + 2 + | ∩ [] |) + | |( − (, )) ≥ Notice that the first part in each of the two sums of (7) and (8) refers to the relation between relation between vertex in ( ) and all the other vertices in ( ). ∈ () and the vertices of the solution set in (i.e., ) while the second part refers to the =| ∩ ()| + 2 | ∖ []| +
| | (, ). ∑︁ |̸= (,)≤ ∑︁ |̸= (,)≤ ∑︁ |̸= (,)≤
| | ∑︁ |̸= (,)≤ ∑︁ |̸= (,)≤ ︂)
(6) = || − | ∩ ()| − 2 | ∖ []| + | | ( − (, )). ∑︁ |̸= (,)≤ Now, we consider that ( ∩ ()) ∩ ( ∖ []) = ∅ and – for ̸∈ it holds ( ∩ ()) ∪ ( ∖ []) = , and – for ∈ it holds ( ∩ ()) ∪ ( ∖ []) = ∖ {}. Then, | ∩ ()| + 2 | ∖ [] | = {︃2|| − | ∩ []| 2|| − 2 − | ∩ []| if ̸∈ ,
∈∩,()( − (, )) ≥ , for each vertex ∈ (), (( − 2) || + | ∩ [] |) + | |( − (, )) ≥
The neighborhood diversity of a graph was introduced by Lampis in [
The following theorem states that the (, )-Broadcast Domination problem is FPT with respect to the neighborhood diversity of the input graph.
We denote by nd the neighborhood diversity of the input graph = (1, . . . , nd). Theorem 4. The (, )-Broadcast Domination (nd5nd+(nd) log ) where = max{, , | ()|}. problem is solvable in time Proof. Denote by the vertex set of . Let be a (, )-Broadcast Dominating set of . For each = 1, . . . , nd, define = ∩ .
In order to give an algorithm solving the (, )-Broadcast Domination problem for , we characterize (7) and (8) for . Let ∈ with 1 ≤ ≤ nd. If is a clique then | ∩ ()| = {︃||
if ̸∈ , || − 1 otherwise.
By (7) and (8) we have If is an independent set then | ∩ ()| = 0 and by (7) and (8) we have By the above inequalities, it is easy to see that an instance ⟨, , ⟩ of (, )-Broadcast Domination has a solution = ⋃︀1≤ ≤ nd with ⊆ if and only if the following Integer Linear Programming has a solution x = (1, . . . , nd) such that consists of any = || vertices ( − 1) || + ( − (, )) ≥ ∀ such that 1 ≤ ≤ nd and is a clique (2) ( − 2) + 2 + ( − (, )) ≥ ∀ such that 1 ≤ ≤ nd and is an ind. set of . The binary variable , indicates whether = or not; in particular, ∈ {0, 1} and by constraints (3)-(4) below, we have that if = 1 then = ||.
min
∑︁ =1,...,nd
(1) ( − 1) + +
(3) ≥ | |
(4) ≤ | |
(5) ∈ {0, 1}
subject to:
∑︁
|̸=
(,)≤
∑︁
∀ = 1, . . . , nd
∀ = 1, . . . , nd
∀ = 1, . . . , nd
To evaluate the time to solve the above ILP, we use a well-known result, stated in [
Question: Is there a vector ∈ Zℓ such that ≥ ? Hence, observing that the considered ILP uses at most 2 nd variables and that the coeficients are upper bounded by = max{, , | ()|}, we have that it can be solved within time (nd5nd+(nd) log ).
Given a graph , the iterated type partition number of , introduced in [
Trivially, for each graph we have itp() ≤ nd(). See also [
In this paper, we will use the following equivalent definition based on the operations (O1)-(O2). Definition 7. A graph has iterated type partition number ℓ ≥ 1 if ℓ is the minimum integer such that = (1, . . . , ℓ) for cographs 1, 2, . . . , ℓ and an outline graph .
We denote by itp the iterated type partition number of the input graph .
v1 v3 v4
M6 v10
M4 v8 M7 (b) v9
M2
M4 M5 Observation 3. We notice that if = (1, . . . , itp) is connected then for each , ∈ () the distance between and in is at most 2, for any = 1, . . . , itp. Indeed, if is connected, then it is a connected cograph and has a diameter at most 2. If is not connected, there exists such that (, ) is an edge in . Hence, and have common neighbors in ( ). Hence, as in Observation 2, the use of the values in Definition 4 is correct.
Using the strategy adopted in Section 4, we are able to compute in time (2 + ) the values (, ′) as well as the corresponding solutions denoted Γ ,′ , for each cograph with = 1, . . . , itp and ′ = 1, . . . , Definition 8. Given a cograph = (, ) and two integers ≥ 2, ≥ 1 we denote by (, ) the value of the largest demand ′ such that there exists a set of size at most (|| ≤ ) and is a (, ′)-Broadcast Dominating set of , where the distance function is redefined as ′(, ) = min(2, (, )), for each , ∈ .
Using the values (, ′) and the solutions Γ ,′ , for each cograph with = 1, . . . , itp and each ′ = 1, . . . , we are able to compute in time () the values (, ) for = 1, . . . , itp and = 1, 2, . . . , | ()|, as well as the corresponding solutions denoted B,. Theorem 5. (, )-Broadcast Domination is solvable in time (itp( + 1)itp+1 + 2 + ). Proof. Algorithm ITP- starting from = 1 increases the budget until a solution is identified. We recall that we are assuming that for each ∈ we have ≤ ∑︀∈()( − (, )), hence the problem does admit a solution.
Fixed a budget , the algorithm considers all the possible vectors s = (1, . . . , itp) where = ∑︀i=tp1 and 0 ≤ ≤ min(, | ()|). For each vector, the algorithm evaluates whether there exists a solution such that || = where = ∩ (), for each 1 ≤ ≤ itp. Specifically, it computes the values ′, corresponding to the residual demand on considering the contribution of nodes in ∖ . Such contribution depends only on the sizes of each with ̸= . Then the values (· , · ) are exploited to check whether each component is able to reach the residual demand ′, using the assigned budget . If this is the case, the solution set is determined in line 4 and returned by the algorithm.
For each = 1, . . . , itp and ∈ () we have (, ) =
∑︁ ∈B, ∩,() ( − (, )) ≥ ′ = −
( − (, )), ∑︁ Algorithm 1: ITP- ( = (1, . . . , itp), , , (· , · ),B· ,· )
Input: A graph = (1, . . . , itp), a radius , a demand , and values (, ) for each = 1, . . . , itp and = 1, . . . , | ()|, with their associated solutions B,.
Output: a solution for the (, )-Broadcast Domination problem for . 1 for = 1 to do 2 for each s = (1, . . . , itp) | ∑︀i=tp1 = and 0 ≤ ≤ 3 for = 1, . . . , itp do ′ = − ∑︁ min(, | ()|) do ( − (, )) 4
|̸= (,)≤ if ⋀︀itp
=1 ( (, ) ≥ ′) then return = ⋃︀i=tp1 B, and consequently
∑︁ ( − (, )) + ∑︁ ⎝
∑︁ ̸= ∈∩,() ∑︁ ( − (, )) + ( − (, )) ≥ .
⎞ ( − (, ))⎠ ⎛ Finally, we notice that Algorithm ITP- requires time (itp ( + 1)itp). Moreover, the time to obtain all the values (, ) and the corresponding solutions B, for = 1, . . . , itp and = 1, 2, . . . , | ()|, is (2 + ).
Let = (1, . . . , itp). In this section, we design an FPT algorithm to solve the (, )Broadcast Domination problem for parameterized by itp and the demand . The algorithm exploits the values (, ′) that can be obtained using the strategy adopted in Section 4, for each cograph with 1 ≤ ≤ itp and ′ = 1, . . . , . We recall that (, 0) = 0, for each cograph .
Theorem 6. (, )-Broadcast Domination is solvable in time (itp ( + 1)itp + 2 + ). Proof. Algorithm ITP- considers all the possible vectors r = (1, . . . , itp), where = 0, . . . , and = 1, . . . , itp, and for each of them verifies if each value satisfies
∑︁ ≥ −
( , )( − (, )).
|̸= (,)≤ Assuming that (9) holds for each in r, select the vertex set (r) = ⋃︀1≤ ≤ itp Γ , , where Γ , ⊆ () is obtained by using the strategy in Section 4 with |Γ , | = (, ). For ∈ () and = 1, . . . , itp, we have ∑︁ (9) (10) ( − (, )) ≥ .
∈Γ, ∩,() |̸= (,)≤ if > ∑︀1≤ ≤ itp (, ) then = Algorithm 2: ITP-( = (1, . . . , itp), , , (· , · ))
Input: A graph = (1, . . . , itp), a radius , a demand , and values (, ′) for each = 1, . . . , itp and ′ = 1, . . . , .
Output: The vector of demands r. 1 = ∞ and r = (0, . . . , 0) 2 for each r = (1, . . . , itp) such that 0 ≤ ≤ , 1 ≤ , ≤ itp do
itp ⎛ ⎞ 3 if ⋀=︁1 ⎜⎝ ≥ − ∑︁ ( , )( − (, ))⎟⎠ then ∑︁ (, ) and r = r 1≤ ≤ itp 4 5 return r; By (9) and (10), it holds
Hence, the set (r) = ⋃︀1≤ ≤ itp Γ , is a (, )-Broadcast Dominating set of .
Furthermore, since Algorithm ITP- returns, among all the vectors r whose components satisfy (9) and (10) for each = 1, . . . , itp, the vector r (see lines 4-5) such that r = arg min |(r)|,
r we can reconstruct the set (r) that is a solution for the instance ⟨, , ⟩ of the (, )Broadcast Domination problem.
Finally, we notice that Algorithm ITP- requires time (itp ( + 1)itp). Moreover the time to obtain all the values (, ′) and the solutions Γ ,′ , for = 1, . . . , itp and ′ = 1, . . . , , is (2 + ).
The (, )-Broadcast Domination problem has been recently introduced and studied in some special classes of graphs (mainly grid graphs and lattices). We have initiated the study of the (, )-Broadcast Domination problem in general graphs. We have designed an approximation algorithm for general graphs and optimal polynomial time algorithms for cographs and graphs of bounded Neighborhood diversity (nd). Moreover, we have presented FPT algorithms parameterized by Iterated type partition number (itp) plus the solution size = || and by itp plus the demand . It eluded us the design of an FPT algorithm for the problem parameterized by itp only, which we leave as an open problem.