论文标题
难于树宽的问题，但易于稳定的问题
Problems hard for treewidth but easy for stable gonality
论文作者
论文摘要
我们表明，当通过路径宽度或树宽参数化时，当XNLP-HARD的某些自然问题（意味着所有t）时，当通过稳定的gonality参数化时，它会fpt，这是一个基于从图到树的最佳图形图的新颖图形参数。我们考虑的问题是经典的流动和定向问题，例如不向下限的无向流（如ITAI所示，这是NP完全完整的），最小最大的最大超级超过（为w [1] - w [1] - 由szeider证明了szeider的范围），由szeider证明了w [1] - 由szeider证明），以及诸如统治（red-lue-blue）的优化问题（诸如quicated（red-Blue）的优化问题（RED-BLUE）（RED-BLUE）是统治（Red-Blue），这是W. Lokshtanov，Saurabh和Villanger）。我们的硬度证明（击败现有结果）使用了最新的XNLP完整问题（接受非确定性检查计数器）。新的简单参数化算法使用了一个新颖的加权树分区概念，其中包括我们称之为Treebreadth的相关参数，灵感来自塞斯的Tree-Partite图概念，以及动态编程和整数线性编程的技术。
We show that some natural problems that are XNLP-hard (which implies W[t]-hardness 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 (which is strongly NP-complete, as shown by Itai), Minimum Maximum Outdegree (for which W[1]-hardness for treewidth was proven by Szeider), and capacitated optimization problems such as Capacitated (Red-Blue) Dominating Set (for which W[1]-hardness was proven by Dom, Lokshtanov, Saurabh and Villanger). Our hardness proofs (that beat existing results) use reduction to a recent XNLP-complete problem (Accepting Non-deterministic Checking Counter Machine). The new easy parameterized algorithms use a novel notion of weighted tree partition with an associated parameter that we call treebreadth, inspired by Seese's notion of tree-partite graphs, as well as techniques from dynamical programming and integer linear programming.
