Problems Hard for Treewidth but Easy for Stable Gonality

Abstract

We show that some natural problems that are XNLP-hard (hence $$\textrm{W}[t]$$ -hard for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph parameter based on optimal maps from graphs to trees. The problems we consider are classical flow and orientation problems, such as Undirected Flow with Lower Bounds, Minimum Maximum Outdegree, and capacitated optimization problems such as Capacitated (Red-Blue) Dominating Set. Our hardness claims beat existing results. The FPT algorithms use a new parameter “treebreadth”, associated to a weighted tree partition, as well as DP and ILP.