Show simple item record

dc.contributor.authorFoucaud, Florent
HAL ID: 169708
dc.contributor.authorGras, Benjamin
dc.contributor.authorPerez, Anthony
HAL ID: 8011
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2020-10-23T13:34:40Z
dc.date.available2020-10-23T13:34:40Z
dc.date.issued2020
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21155
dc.language.isoenen
dc.subjectBroadcast domination
dc.subjectDominating set
dc.subjectMultipacking
dc.subjectDirected graphs
dc.subjectParameterized complexity
dc.subject.ddc005en
dc.titleOn the Complexity of Broadcast Domination and Multipacking in Digraphs
dc.typeCommunication / Conférence
dc.description.abstractenWe 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 f:V(D)→N such that for each vertex v of D, there exists a vertex t with f(t)>0 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.
dc.identifier.citationpages264-276
dc.relation.ispartoftitleCombinatorial Algorithms - 31st International Workshop
dc.relation.ispartofeditorLeszek Gąsieniec, Ralf Klasing, Tomasz Radzik
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofurl10.1007/978-3-030-48966-3
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-02793880
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-030-48966-3
dc.relation.conftitleCombinatorial Algorithms, 31st International Workshop, IWOCA 2020
dc.relation.confdate2020
dc.relation.confcountryFRANCE
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-48966-3_20
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-12-17T09:13:19Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record