Pragmatic Parameterized Algorithms

固定参数和中等指数算法的范例在获得许多NP-完全问题的有效算法方面已经取得了惊人的成功。然而，这些算法中的许多都纯粹是理论上的，因为它们不能在现实世界中实现，即在严格的时间和成本约束下。例如，有一些算法依赖于算法元定理-结果不仅适用于少数几个孤立的问题，而且适用于整个类别的问题。虽然元定理在快速确定手头的问题是否允许特殊类型的算法时非常有用，但它们在实际中设计算法时通常不是很有用。此外，还有使用深层结构定理的算法，如图的次要定理。这样的算法也是不可实现的。最后，还有一些算法使用本身很难计算的结构参数。有效的FPT算法WRT这些参数在实践中可能不是有效的。这个项目的广泛目标是弥合纯理论算法和启发式算法之间的差距，这些算法在实践中被广泛使用，但产生的解决方案没有任何质量保证。特别是，我们寻求开发高效的算法，这些算法(1)可以很容易地翻译成程序并在现实世界的约束下成功运行；(2)在渐近行为方面与当前最好的算法竞争，甚至更快。我们的主要目标是改进和创造新的算法技术，以便向可实施性迈进一步。这些新的算法技术本身是复杂的或具有元定理的味道，但我们感兴趣的是那些服从于实现的技术。我们考虑的现实世界限制包括实现时间、空间要求和运行时间保证。通过提供透明的时间和空间界限，即通过将多项式和常数因子保持在合理的限度内，我们希望推动最终可用于工业和应用的算法的极限。

The paradigms of fixed-parameter and moderately exponential algorithmshave been spectacularly successful in obtaining efficient algorithms fora number of NP-complete problems. Many of these algorithms are, however,purely theoretical in the sense that they are not implementable in areal-world setting, i.e., under tight time and cost constraints. Forinstance, there are algorithms that rely on algorithmic meta-theorems - results that hold not just for a few isolated problemsbut for a whole class of problems. While meta-theorems are immensely useful inquickly establishing whether a problem at hand admits an algorithm of aparticular type, they are usually not very useful in designing algorithmsin practice. Then again there are algorithms that use deep structural theoremssuch as the Graph Minors Theorem. Such algorithms are not implementable either. Finally there are algorithms that use structural parameters that are themselves hardto compute. Efficient FPT-algorithms wrt these parameters might not be efficient in practice. The broad goal of this project is to bridge the gap between purely theoretical algorithmsand heuristics that are extensively used in practice but which produce solutions without any quality guarantee. In particular, we seek to develop efficient algorithms that are (1) easily translatable into programs and run successfully under real-worldconstraints; and, (2) competitive with or even faster than the currentbest algorithms in their asymptotic behavior. Our main aim is to improve and create new algorithmic techniques in order to take a stepforward towards implementability. These new algorithmic techniques themselves be complex or have the flavor of meta-theorems but we areinterested in those which are amenable to implementation.The real-world constraints we have in mind include implementation time,space requirements and running time guarantees. By providing transparenttime and space bounds, i.e., by keeping polynomial and constants factorswithin reasonable limits, we wish to push the envelope of algorithmsthat can eventually be engineered for use in industry andapplications.