Manolis Vasilakis

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...

Michael Lampis, Manolis Vasilakis

Capacitated Vertex Cover is the hard-capacitated variant of Vertex Cover: given a graph, a capacity for every vertex, and an integer $k$, the task is to select at most $k$ vertices that cover all edges and assign each edge to one of its chosen endpoints so that no chosen vertex receives more incident edges than its capacity. This problem is a classical benchmark in parameterized complexity, as it was among the first natural problems shown to be W[1]-hard when parameterized by treewidth. We revisit its exact complexity from a fine-grained parameterized perspective and obtain a much sharper picture for several standard parameters. For the natural parameter $k$, we prove under the Exponential Time Hypothesis (ETH) that no algorithm with running time $k^{o(k)} n^{\mathcal{O}(1)}$ exists. In particular, this shows that the known algorithms with running time $k^{\mathcal{O}(\mathrm{tw})} n^{\mathcal{O}(1)}$ are essentially optimal. We then turn to more general structural parameters. For vertex cover number $\mathrm{vc}$, we give evidence against a $2^{\mathcal{O}(\mathrm{vc}^{2-\varepsilon})} n^{\mathcal{O}(1)}$ algorithm, as such an improvement would imply corresponding progress for a broader class of integer-programming-type problems. We complement this barrier with a nearly matching upper bound for vertex integrity $\mathrm{vi}$, improving the previously known double-exponential dependence to an algorithm with running time $\mathrm{vi}^{\mathcal{O}(\mathrm{vi}^{2})} n^{\mathcal{O}(1)}$ using $N$-fold integer programming. For treewidth, we show that the standard dynamic programming algorithm with running time $n^{\mathcal{O}(\mathrm{tw})}$ is essentially optimal under the ETH, even if one parameterizes by tree-depth. Turning to clique-width, we prove that Capacitated Vertex Cover remains NP-hard already on graphs of linear clique-width $6$...