Problems Hard for Treewidth but Easy for Stable Gonality

被引：5

作者：

Hans, L. Bodlaender ^{[1
]}

Cornelissen, Gunther ^{[2
]}

Van der Wegen, Marieke ^{[2
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, Princetonpl 5, NL-3584 CC Utrecht, Netherlands

[2] Univ Utrecht, Dept Math, POB 80010, NL-3508 TA Utrecht, Netherlands

来源：

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022) | 2022年 / 13453卷

关键词：

Parameterized complexity; Graph algorithms; Network flow; Graph orientation; Capacitated dominating set; Tree partitions; Stable gonality; GRAPHS; COMPLEXITY;

D O I：

10.1007/978-3-031-15914-5_7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that some natural problems that are XNLP-hard (hence 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.

引用

页码：84 / 97

页数：14