| Title | : | Broadcast Domination and Multipacking in (di)graphs |
| Speaker | : | Florent Foucaud (Associate Professor @ Clermont Auvergne University, France) |
| Details | : | Thu, 18 Jan, 2024 11:00 AM @ SSB-334 |
| Abstract: | : | A dominating broadcast of a (di)graph $G$ is an assignment $f$ of non-negative integer weights to the vertices of $G$, such that each vertex $x$ with $f(x)=0$ is at (directed) distance at most $r$ from some vertex $y$ with $f(y)geq r$. The broadcast domination number of graph $G$ is the smallest cost (i.e. sum of all weights) of a dominating broadcast of $G$. This concept models a natural covering problem in telecommunications, where the graph represents a network and $f(x)$ is the emission power of a radio station; all nodes of the network must be covered by some radio station. Its nice feature is that, as shown by Heggernes and Lokshtanov in 2006, an optimal dominating broadcast can be computed in polynomial time (provided the graph is undirected), unlike most standard covering problems. We first discuss the integrality gap (for undirected graphs) between the optimum solutions of Broadcast Domination and its recently introduced dual problem, called Multipacking, for general graphs and for chordal graphs. Then, we focus on algorithmic questions. It turns out that both problems are NP-hard on directed graphs, and they are also hard in the realm of parameterized complexity, for the parameter solution cost. We present some polynomial-time and parameterized algorithms for special classes of digraphs. |
