2024/10/10 by Michael Lampis, Valia Mitsou, Lampis, Michael +9
Computer Science · Engineering · #Advanced Optical Network Technologies #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2410.08314
openalex publication_date 2024/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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∈ T is the number of edges uv∈ 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 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...