Edouard Nemery

Michael Lampis, Valia Mitsou, Edouard Nemery et al.

In this paper we study the Spanning Tree Congestion problem, where we are given a graph $G=(V,E)$ and are asked to find a spanning tree $T$ of minimum maximum congestion. Here, the congestion of an edge $e\in T$ is the number of edges $uv\in E$ such that the (unique) path from $u$ to $v$ in $T$ traverses $e$. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results. We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form ``vertex-deletion distance to class $\mathcal{C}$'', thus obtaining W[1]-hardness for parameters more restricted than treewidth, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on interval graphs of modular-width $4$. Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. Complementing the problem's W[1]-hardness for treewidth...

Joanne Dumont, Edouard Nemery, Anthony Perez et al.

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.