Efficient Pre-Processing of Hard Problems: New Approaches, Basic Theory and Applications

计算机存储了关于人类和工业活动各个方面的更大量的数据。然而，它们在解决优化和搜索中的常见问题方面并没有变得更好。传统的复杂性理论表明，这些问题中的许多问题需要的算法是不太可能存在的。参数化的复杂性方法使我们能够获得非常有效的算法，为各种各样的问题，但所需的机器是多样化和复杂的。这项研究将把机器组织成一种新的方法，通过对问题域的参数进行简化，系统地找到好的算法。其结果是，有效的算法获得了许多不同的领域。

Computers store even larger amounts of data about all aspects of human and industrial activity. However, they have not become significantly better at solving common problems in optimization and search. Traditional complexity theory indicates many of these problems require algorithms that are very unlikely to exist. The Parameterized Complexity approach allows us to obtain very efficient algorithms for a large variety of problems, but the machinery required was diverse and complicated. This research will organize the machinery into a new approach that systematically finds good algorithms by applying simplifications around a parameter of the domain of the problem. As a result, efficient algorithms are obtained for many diverse areas.