key: cord-0044025-vp13ppbp
authors: Foucaud, Florent; Gras, Benjamin; Perez, Anthony; Sikora, Florian
title: On the Complexity of Broadcast Domination and Multipacking in Digraphs
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_20
sha: 2fb0aaeac4074af223b3f63a80f93f7ac14f0851
doc_id: 44025
cord_uid: vp13ppbp

We study the complexity of the two dual covering and packing distance-based problems Broadcast Domination and Multipacking in digraphs. A dominating broadcast of a digraph D is a function [Formula: see text] such that for each vertex v of D, there exists a vertex t with [Formula: see text] having a directed path to v of length at most f(t). The cost of f is the sum of f(v) over all vertices v. A multipacking is a set S of vertices of D such that for each vertex v of D and for every integer d, there are at most d vertices from S within directed distance at most d from v. The maximum size of a multipacking of D is a lower bound to the minimum cost of a dominating broadcast of D. Let Broadcast Domination denote the problem of deciding whether a given digraph D has a dominating broadcast of cost at most k, and Multipacking the problem of deciding whether D has a multipacking of size at least k. It is known that Broadcast Domination is polynomial-time solvable for the class of all undirected graphs (that is, symmetric digraphs), while polynomial-time algorithms for Multipacking are known only for a few classes of undirected graphs. We prove that Broadcast Domination and Multipacking are both NP-complete for digraphs, even for planar layered acyclic digraphs of small maximum degree. Moreover, when parameterized by the solution cost/solution size, we show that the problems are respectively W[2]-hard and W[1]-hard. We also show that Broadcast Domination is FPT on acyclic digraphs, and that it does not admit a polynomial kernel for such inputs, unless the polynomial hierarchy collapses to its third level. In addition, we show that both problems are FPT when parameterized by the solution cost/solution size together with the maximum out-degree. Finally, we give for both problems polynomial-time algorithms for some subclasses of acyclic digraphs.

to its broadcast domination number [5] . Equality holds for many graphs, such as strongly chordal graphs [4] . Consider the following computational problem.

• Input: A digraph D = (V, A), an integer k ∈ N.

• Question: Does there exist a multipacking S ⊆ V of D of size at least k?

Known Results. In contrast with most graph covering problems, which are usually NP-hard, Heggernes and Lokshtanov designed in [17] (see also [21] ) a sextic-time algorithm for Broadcast Domination in undirected graphs. This intriguing fact has motivated research on further algorithmic aspects of the problem. For general undirected graphs, no faster algorithm than the original one is known. A quintic-time algorithm exists for undirected series-parallel graphs [2] . An analysis of the algorithm for general undirected graphs gives quartic time when it is restricted to chordal graphs [17, 18] , and a cubic-time algorithm exists for undirected strongly chordal graphs [4] . The problem is solvable in linear time on undirected interval graphs [7] and undirected trees [4, 9] (the latter was extended to undirected block graphs [18] ).

Regarding Multipacking, to the best of our knowledge, its complexity is currently unknown, even for undirected graphs (an open question posed in [24, 25] ). However, there exists a polynomial-time (2 + o(1))-approximation algorithm for all undirected graphs [1] . Multipacking can be solved with the same complexity as Broadcast Domination for undirected strongly chordal graphs, see [4] . Improving upon previous algorithms from [22, 24] , the authors of [4] give a simple linear-time algorithm for undirected trees.

Our Results. We study Broadcast Domination and Multipacking for directed graphs (digraphs), which form a natural setting for not necessarily symmetric telecommunication networks. In contrast with undirected graphs, we show that Broadcast Domination is NP-complete, even for planar layered acyclic digraphs (defined afterwards) of maximum degree 4. This holds for Multipacking, even for planar layered acyclic digraphs of maximum degree 3, or acyclic digraphs with a single source and maximum degree 5. Moreover, when parameterized by the solution cost/solution size, we prove that Broadcast Domination is W[2]-hard (even for bipartite digraphs without directed 2-cycles) and Multipacking is W[1]-hard. On the positive side, we show that Broadcast Domination is FPT on acyclic digraphs (DAGs for short) but does not admit a polynomial kernel for layered DAGs, unless the polynomial hierarchy collapses to its third level. Moreover, we show that both Broadcast Domination and Multipacking are polynomial-time solvable for layered DAGs with a single source. We also design FPT algorithms for both problems when parameterized by the solution cost/solution size together with the maximum out-degree. The resulting complexity landscape is represented in Fig. 1 . We start with some definitions in Sect. 2. We prove our results for Broadcast Domination in Sect. 3. The results for Multipacking are presented in Sect. 4. We conclude in Sect. 5. Due to lack of space, we omit some proofs that can be found in the full version of the paper [14] . 

Directed Graphs. We mainly consider digraphs, usually denoted D = (V, A) 1 , where V is the set of vertices and A the set of arcs. For an arc uv ∈ A, we say that v is an out-neighbor of u, and u an in-neighbor of v. Given a subset of vertices V ⊆ V , we define the digraph induced by V as D = (V , A ) where A = {uv ∈ A : u ∈ V and v ∈ V }. We denote such an induced subdigraph by D [V ] . A directed path from a vertex p 1 to p l is a sequence {p 1 , . . . , p l } such that p i ∈ V and p i p i+1 ∈ A for every 1 i < l. When p 1 = p l , it is a directed cycle. A digraph is acyclic whenever it does not contain any directed cycle as an induced subgraph. An acyclic digraph is called a DAG for short. The (open) out-neighborhood of a vertex v ∈ V is the set N + (v) = {u ∈ V : vu ∈ A}, and its closed out-neighborhood is N

We define similarly the open and closed in-neighborhoods of v and denote them by

For the sake of readability, we always mean out-neighborhood when speaking of the neighborhood of a vertex. A DAG D = (V, A) is layered when its vertex set can be partitioned into {V 0 , . . . , V t } such that N − (V 0 ) = ∅ and N + (V t ) = ∅ (vertices of V 0 and V t are respectively called sources and sinks), and uv ∈ A implies that u ∈ V i and v ∈ V i+1 , 0 i < t. A single-sourced layered DAG is a layered DAG with only one source, that is, satisfying |V 0 | = 1. A digraph is bipartite or planar if its underlying undirected graph has the corresponding property. Every layered digraph is bipartite. Given two vertices u and v, we denote by d(u, v) the length of a shortest directed path from u to v. For a vertex v ∈ V and an integer d, we define the ball of radius d centered at

A parameterized problem is a decision problem together with a parameter, that is, an integer k depending on the instance. A problem is fixed-parameter tractable (FPT for short) if it can be solved in time f (k) · |I| c for an instance I of size |I| with parameter k, where f is a computable function and c is a constant. Given a parameterized problem P , a kernel is a function which associates to each instance of P an equivalent instance of P whose size is bounded by a function h of the parameter. When h is a polynomial, the kernel is said to be polynomial. An FPT-reduction between two parameterized problems P and Q is a function mapping an instance (I, k) of P to an instance (f (I), g(k)) of Q, where f and g are computable in FPT time with respect to parameter k, and where I is a YES-instance of P if and only if f (I) is a YESinstance of Q. When moreover f can be computed in polynomial time and g is polynomial in k, we say that the reduction is a polynomial time and parameter transformation [3] . Both reductions can be used to derive conditional lower bounds: if a parameterized problem P does not admit an FPT algorithm (resp. a polynomial kernel) and there exists an FPT-reduction (resp. a polynomial time and parameter transformation) from P to a parameterized problem Q, then Q is unlikely to admit an FPT algorithm (resp. a polynomial kernel). Both implications rely on certain standard complexity hypotheses; we refer the reader to the book [8] for details.

Theorem 1. Broadcast Domination is NP-complete, even for planar layered DAGs of maximum degree 4.

Proof (sketch). We provide a reduction from the W[2]-hard Multicolored Dominating Set problem [6] .

Construction. We build an instance (D = (V , A ), k ) of Broadcast Domination as follows. To obtain the vertex set V , we multiplicate V into four sets V 0 , V 1 , V 2 and V 3 and we will have a set M of subdivided vertices. The set V 0 ∪ V 1 will induce an oriented complete bipartite graph, while V 2 ∪ V 3 will induce a matching. For a vertex v ∈ V , 0 i 3, its copy in V i is denoted v i . We assume that |V i | 2, since otherwise one must take the only vertex in V i . For each 1 i k we then add the following arcs:

Moreover, for every edge vw in G, we add an arc from v 1 to w 2 , and we subdivide it once. The set of all subdivision vertices is called M . Finally, we set k = 3k. Digraph D has no directed 2-cycles, and is bipartite with sets

One can check that G has a multicolored dominating set of size k if and only if D has a dominating broadcast of cost 3k.

We now address the special cases of (layered) DAGs. Note that Dominating Set remains W[2]-hard on DAGs by a reduction from [23, Theorem 6.11.2]. In contrast, we now give an FPT algorithm for Broadcast Domination on DAGs that counterbalances the W[2]-hardness result. Proof. The proof relies on the following proposition, which is reminiscent of a stronger statement of Dunbar et al. [11] for undirected graphs (stating that there always exists an optimal dominating broadcast where each vertex is covered exactly once, which is false for digraphs). Proof. Let f be an optimal dominating broadcast of D, and assume there exists

and f u (v) = 0, implying that the cost of f u is at most the cost of f .

We can now prove Theorem 3. Let D = (V, A) be a DAG. We consider the set V 0 of sources of D. Observe that for every s ∈ V 0 , f(s) 1 must hold. In particular, this means that |V 0 | k (otherwise we return NO). We provide a branching algorithm based on this simple observation and on Proposition 4. We start with an initial broadcast f consisting of setting f (s) = 1 for every vertex s in V 0 . At each step of the branching algorithm, we let

be the set of currently covered vertices, and we consider the digraph

Notice that D f is acyclic and hence contains a source u. Since every vertex of N f \ V f is covered, we may assume by Proposition 4 that in the sought optimal solution, u is only covered by itself or by a vertex in V f . This means that one needs to branch on at most k + 1 distinct cases: either setting f (u) = 1, or increasing the cost of one of its at most k broadcasting ancestors in V f . At every branching, the parameter k decreases by 1, which ultimately gives an O * (2 k log k )-time algorithm and completes the proof of Theorem 3.

We will now complement the previous result by a negative one, which can be proved using a reduction from Hitting Set, defined as follows.

Hitting Set • Input: A universe U of elements, a collection F of subsets of U , an integer k ∈ N. Proof (sketch). Let D = (V, A) be a single-sourced layered DAG with layers {V 0 , . . . , V t }. For the sake of readability, sets V i such that |V i | = 1 are denoted s i , for 0 i t. Due to lack of space, the following claim is given without proof.

There always exists an optimal dominating broadcast f of D such that:

where l = j − i − 1 and j is the smallest index such that j i + 2 and |V j | = 1.

We thus deduce a simple top-down procedure to compute an optimal dominating broadcast f . We start with setting i = 0. While there remain uncovered vertices, we let f (s i ) = j − i − 1 for the smallest value j such that s j exists and j i + 2. In other words, s i will cover all vertices below it, until the closest vertex of the set t j=0 s j that is not a neighbour of s i . We then carry on by setting i = j. By Claim 1, this leads to f being an optimal dominating broadcast.

We finally give an FPT algorithm for two parameters. By Theorems 1 and 2, such a result probably does not hold for each of them individually.

We will need the following results to prove our results for Multipacking. The first one was proved for undirected graphs in [16] . Proof. It suffices to select every third vertex on the path.

The following lemma is the central result of both our polynomial-time algorithm (Theorem 14) and NP-completeness reduction (Theorem 12).

Proof. Let S ⊆ V be a multipacking of D of maximum size. By definition of a multipacking, considering each ball centered at the source s, the following holds for every 1 i t:

We will prove the result inductively, by locally modifying S in a top-down manner until it has the desired property. Let j 2 be the smallest index such that |S ∩ V j | 2, and i < j be the largest index such that |S ∩ V i | = 0. Notice that i is well-defined due to (1) . Moreover, let s 1 j and s 2 j be two vertices of S ∩ V j . Case 1. We assume first that i = j − 1. Let u 1 i and u 2 i be vertices of V i such that u 1 i s 1 j and u 2 i s 2 j belong to A (note that in a layered DAG every non-source vertex has a predecessor in the previous layer). Since S is a multipacking, we have Assume for a contradiction that this is the case. This means that s i−1 is within distance j − (i − 1) of every vertex contained in ∪ j l=i V l . By the choice of indices i and j we know that ∪ j l=i V l contains at least j − (i − 1) vertices from S, which in turn implies that B + j−(i−1) (s i−1 ) ∩ S = j − (i − 1) + 1, contradicting (1). Thus, there is a vertex v i in V i that has no in-neighbor in S. Now, we know by choices of i and j that |S ∩ V p | = 1 for i < p < j. Hence the set

, is a multipacking of D having the same size than S. By iterating the above argument, we end up with i = j − 1, in which case we can apply the argument from Case 1. Overall, after each iteration of Case 1, j strictly increases. The procedure terminates when the value of j reaches t.

Theorem 11. Multipacking is NP-complete, even for planar layered DAGs of maximum degree 3.

Multipacking is NP-complete on single-sourced DAGs of maximum degree 5.

Proof (sketch). We provide a reduction from the NP-complete Independent Set problem [15] . We define the function f : To conclude, one can see that G has an independent set of size k if and only if D has a multipacking of size k = k + 2m + 1.

Proof (sketch). We provide an FPT-reduction from Multicolored Independent Set, which is W[1]-hard when parameterized by k [8] .

• Question: Does there exist an independent set S of G s.t. |S ∩ V i | = 1 for 1 i k?

Construction. We construct an instance (D = (V , A ) , k ) of Multipacking as follows. We consider the bipartite incidence graph of G, that is we add V ∪E to V . To construct A , we add an arc from a vertex e ∈ E to a vertex v ∈ V if and only if e contains v. We next group vertices of E into k 2 sets E i,j , 1 i < j k according to the colors of their corresponding endpoints, and add every possible arc within each set E i,j . We next duplicate the vertices of each set V i into a set V i such that there is an arc from each vertex v i ∈ V i to its corresponding copy v i in V i . Finally, we add k vertices {s 1 , . . . , s k } such that there is an arc from s i to every vertex of V i . Notice in particular that the maximum finite distance is 3. To conclude, one can see that the graph G has a multicolored independent set of size k if and only if the digraph D has a multipacking of size k = 2k + k 2 .

Theorem 14. Multipacking can be solved in linear time on single-sourced layered DAGs.

Proof. Let D = (V, A) be a single-sourced layered DAG. By Lemma 10, in every single-sourced layered DAG there is a multipacking of maximum size that is a maximum-size set of vertices with at most one vertex per layer such that two chosen vertices of consecutive layers are not adjacent. We give a polynomial-time bottom-up procedure to find such a set. At each step of the procedure, a layer V i is partitioned into a set of active vertices and a set of universal ones, denoted respectively A i and U i . Our goal is to select exactly one vertex in each set of active vertices. We initiate the algorithm by setting A t = V t and U t = ∅. Now, for every i with 0 i < t, we set

In other words, U i contains the vertices of layer V i that are adjacent to all active vertices of V i+1 . During the procedure, if some layer V i satisfies A i = ∅, we let A i−1 = V i−1 and repeat this process until V 0 is reached.

To construct a maximum multipacking, we start from V 0 , and for each 0 i t we pick a vertex s i in each non-empty set A i of active vertices. Every time a vertex s i is picked, we remove its closed neighborhood from D. By construction, every time a vertex s i is picked, there exists a vertex s i+1 ∈ A i+1 such that s i s i+1 does not belong to A (otherwise s i would belong to U i ). To prove the optimality of our algorithm, let 0 i < t be such that A i = ∅, and j > i be the smallest integer greater than i such that V j = A j . Such a j exists since A t = V t . Claim 2. Let S be a multipacking with at most one vertex per layer. Then:

Proof. Let S be an optimal multipacking with at most one vertex per layer. Assume by contradiction that S ∩ j k=i V k > j − i + 1, and call s k the vertex in V k ∩ S for every i k j. We know that s i ∈ U i , and since every vertex in A i+1 is an out-neighbor of s i , then s i+1 ∈ U i+1 . By induction, for every i k j, we have s k ∈ U k , but U j = ∅ by choice of j, leading to a contradiction.

Note that Claim 2 gives one less vertex than what Lemma 10 implies, and that it is the value reached by our algorithm, since for i k j, the only layer with U k = V k is V i . The sets of active and universal vertices can be constructed by standard graph searching, so the whole algorithm takes O(|V | + |A|) time.

Multipacking parameterized by solution size k and maximum out-degree d is FPT.

Proof. Let (D = (V, A), k) be an instance of Multipacking such that D has maximum out-degree d. By Lemma 8, if D has a shortest directed path of length 3k − 3, we can accept the input (this can be checked in polynomial time). Thus, we can assume that the length of any shortest path is at most 3k−2. If a vertex u has a directed path to a vertex v, we say that u absorbs v, and a set S of vertices is absorbing if every vertex in D is absorbed by some vertex of S. If D has a set of k vertices, no two of which are absorbed by some common vertex (e.g. a set of k sources), we can accept, since this set forms a valid solution. Note that this property is satisfied by any minimum-size absorbing set S: indeed, if some vertex w absorbs two vertices u, v of S, we may replace them by w and obtain a smaller absorbing set, a contradiction. We claim that we can find a minimumsize absorbing set in FPT time. Indeed, we can reduce this problem to Hitting Set (defined for the proof of Theorem 5) as follows. We let U = V (D), and F contains a set F v for every vertex v, where F v comprises every vertex which absorbs v (including v itself). Because D has out-degree at most d and the length of any shortest path is at most 3k − 2, every vertex of U is contained in at most d U = 3k−2 i=0 (d − 1) i + 1 sets of F. Moreover, a set of vertices of U = V (D) is a hitting set of (U, F) if and only if it is an absorbing set of D. We can solve Hitting Set in FPT time when parameterized by d U and solution size k [19] , which proves the above claim. As mentioned before, if the obtained minimumsize absorbing set of D has size at least k, since it forms a valid multipacking, we can accept. Otherwise, D can be covered by k − 1 balls of radius at most 3k − 2. Each ball has at most 3k−2 i=0 (d − 1) i + 1 = d O(k) vertices, so in total D has at most d O(k) vertices and a brute-force algorithm is FPT.

We have studied Broadcast Domination and Multipacking on various subclasses of digraphs, with a focus on DAGs. It turns out that they behave very differently than for undirected graphs. We feel that Multipacking is slightly more challenging. Indeed, some problems that we solved for Broadcast Domination are open for Multipacking. For example, it would be interesting to see whether Multipacking is FPT for DAGs, and whether it remains W[1]-hard for digraphs without directed 2-cycles. It is also unknown whether Multipacking is NP-hard on undirected graphs, as asked in [24, 25] . On the other hand, we showed that Multipacking is NP-complete for single-sourced DAGs, but we do not know whether the same holds for Broadcast Domination. It is not difficult to show that both problems are FPT when parameterized by the vertex cover number. What about smaller parameters such as tree-width or DAG-width?

Broadcast domination and multipacking: bounds and the integrality gap

Broadcast domination algorithms for interval graphs, series-parallel graphs, and trees

Kernel bounds for disjoint cycles and disjoint paths

Broadcast domination and multipacking in strongly chordal graphs

New bounds for the broadcast domination number of a graph

Resolving Conflicts for lower-bounded clustering

A linear-time algorithm for broadcast domination problem on interval graphs

Parameterized Algorithms

A linear-time algorithm for broadcast domination in a tree

Kernelization lower bounds through colors and IDs

Broadcasts in graphs

Dominating broadcasts in graphs

Cost domination in graphs

On the complexity of broadcast domination and multipacking in digraphs

Computers and Intractability

On the difference between broadcast and multipacking numbers of graphs

Optimal broadcast domination in polynomial time

Broadcast domination on block graphs in linear time

Weak compositions and their applications to polynomial lower bounds for kernelization

Introduction to Combinatorial Mathematics

Broadcast domination

Broadcasts and multipackings in trees

Width-measures for directed graphs and algorithmic applications

Broadcasts and multipackings in graphs

New results on broadcast domination and multipacking

Acknowledgements. FF is partially funded by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39) and by the ANR project HOSIGRA (ANR-17-CE40-0022). FS is partially supported by the project ESIGMA (ANR-17-CE23-0010).