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.
翻译:许多计算问题都承认特殊投入的快速算法,然而,所需要的属性可能相当严格。例如,许多图形问题在间隔或比词表上或小模块-宽度或小树宽度的图形上比在一般图表上可以更快地解决。一个挑战是如何实现这种结果的最普遍性,即适用于限制性较低的输入类别,而不会在运行时间方面损失很多。在使用代数表达式的基础上,我们提出了一个将这种同质结构合并成更复杂的混合结构的清洁和稳健的方法,我们用这种方法来显示模块-宽度、树深度和模块-树深度自然概念的组合。我们为设计在创建的图形类别上的高效参数化算法提供了一个通用框架,目的是获得与同质案例相匹配的竞争性运行时间。为了显示我们给负周期探测、Vertex-weighted All-Pairs最短路径和三角计数的参数化算法的实用性。