论文标题
具有异质结构的图表上有效的参数化算法：结合树深度和模块化宽度
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width
论文作者
论文摘要
许多计算问题承认特殊输入的快速算法，但是，所需的属性可能非常限制。例如，与一般图相比，在间隔或cographs或小模块化宽度或小树宽度的图形上，可以更快地解决许多图形问题。一个挑战是达到此类结果的最大一般性，即适用于较小的限制性输入类，而不会在运行时间方面损失太多。 在使用代数表达式的基础上，我们提出了一种将这种均匀结构结合到更复杂的异质结构中的干净，坚固的方式，我们将其显示为模块化，树深度和模块化树深度的自然概念的结合。我们提供了一个通用框架，用于在创建的图形类上设计有效的参数化算法，旨在获得与均匀案例相匹配的竞争运行时间。为了显示适用性，我们为负周期检测，顶点加权的全对最短路径和三角计数提供了有效的参数化算法。
Many computational problems admit fast algorithms on special inputs, however, the required properties might be quite restrictive. E.g., many graph problems can be solved much faster on interval or cographs, or on graphs of small modular-width or small tree-width, than on general graphs. One challenge is to attain the greatest generality of such results, i.e., being applicable to less restrictive input classes, without losing much in terms of running time. Building on the use of algebraic expressions we present a clean and robust way of combining such homogeneous structure into more complex heterogeneous structure, and we show-case this for the combination of modular-width, tree-depth, and a natural notion of modular tree-depth. We give a generic framework for designing efficient parameterized algorithms on the created graph classes, aimed at getting competitive running times that match the homogeneous cases. To show the applicability we give efficient parameterized algorithms for Negative Cycle Detection, Vertex-Weighted All-Pairs Shortest Paths, and Triangle Counting.
