Eiben Eduard, Ganian Robert, Szeider Stefan
Algorithms and Complexity Group, TU Wien, Vienna, Austria.
Algorithmica. 2018;80(2):742-771. doi: 10.1007/s00453-017-0290-8. Epub 2017 Feb 13.
A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are more powerful for fixed-parameter algorithms than the cardinality of modulators and rank-width itself. Then, we develop a fixed-parameter algorithm for finding such well-structured modulators to every graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for Minimum Vertex Cover and Maximum Clique. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for deciding problems expressible in monadic second order logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems.
图中的一个调制器是一个顶点集，删除该顶点集可使所考虑的图属于某个特定的图类。长期以来，到各种图类的调制器的基数一直被用作一种结构参数，可用于为一系列难题获得固定参数算法。在这里，我们研究当一个图包含一个很大但“结构良好”（从具有有界秩宽的意义上来说）的调制器时会发生什么。这样的调制器是否仍然可以用于获得高效算法？甚至有可能有效地找到这样的调制器吗？我们首先表明，从这种结构良好的调制器导出的参数对于固定参数算法来说比调制器的基数和秩宽本身更强大。然后，我们开发了一种固定参数算法，用于为每个可以由有限的禁止导出子图集合来表征的图类找到这种结构良好的调制器。我们通过展示如何使用结构良好的调制器来为最小顶点覆盖和最大团问题获得高效的参数化算法来进行。最后，我们使用结构良好的调制器的概念来开发一个用于判定用一元二阶逻辑可表达的问题的算法元定理，并证明这个结果在不能推广到线性一元二阶逻辑（LinEMSO）问题的意义上是紧密的。
