参数化算法：研究生与本科生教材

"Parameterized Algorithms(英文版)" 是一本由Marek Cygan、Fedor V. Fomin等多位专家合著的专业教材，专注于参数化算法的理论与实践。这本书不仅适用于初学者，也适合对参数化算法有深入研究的研究生和高年级本科生。 参数化算法是一种算法设计策略，它关注问题的输入中某些特定参数的影响，而不是仅仅考虑输入的整体规模。这种分析方法能够为某些看似困难的问题提供实用的解决方案，即使在最坏情况下的运行时间仍然保持在多项式级别，只要输入的参数是较小的。 书籍分为三个主要部分： 1. **基础技术**：这部分为读者提供了参数化算法的基础知识，涵盖各种算法范式。这些章节适合作为固定参数易处理性（FPT，Fixed-Parameter Tractability）的入门教程。在这里，读者将学习如何利用关键工具如树分解、割点、分支定理等来设计和分析算法。 2. **高级算法思想**：第二部分深入探讨了更先进的算法技术，反映了参数化算法领域的最新进展。其中包括应用重要分离器、基于线性规划的分支策略、Cut & Count方法以优化树分解算法，以及利用拟阵族和强指数时间假设进行的算法设计。这部分内容将引导读者进入研究前沿。 3. **复杂性理论**：第三部分则关注参数化算法的复杂性理论，包括对W[1]-硬度的讨论，指数时间假设的探讨，以及关于核化下界的证明。这些章节提供了负面证据，展示了在某些情况下问题固有的困难性。 每章都配备有练习题和提示，旨在帮助读者巩固理解并引导他们进一步探索原始文献和相关工作。全书以易于理解的方式重新阐述了许多经典结果，使之更适合教学和自学。 《Parameterized Algorithms》是学习和研究参数化算法的宝贵资源，它为读者提供了丰富的算法工具箱，并引领他们进入这个充满挑战和机遇的研究领域。无论是对于学术研究还是实际应用，这本书都能提供扎实的理论基础和实用的技巧。