The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (Lecture Notes in Computer Science, 7370)

Parameterized complexity is currently a thriving field in complexity theory and algorithm design. A significant part of the success of the field can be attributed to Michael R. Fellows. This Festschrift has been published in honor of Mike Fellows on the occasion of his 60th birthday. It contains 20 papers that showcase the important scientific contributions of this remarkable man, describes the history of the field of parameterized complexity, and also reflects on other parts of Mike Fellows’s unique and broad range of interests, including his work on the popularization of discrete mathematics for young children. The volume contains several surveys that introduce the reader to the field of parameterized complexity and discuss important notions, results, and developments in this field. Front Matter....Pages - Front Matter....Pages 1-1 Fixed-Parameter Tractability, A Prehistory,....Pages 3-16 The Birth and Early Years of Parameterized Complexity....Pages 17-38 Crypto Galore!....Pages 39-50 Flyby: Life Before, During, and After Graduate Studies with Mike Fellows....Pages 51-55 The Impact of Parameterized Complexity to Interdisciplinary Problem Solving....Pages 56-68 Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows....Pages 69-73 Mike Fellows: Weaving the Web of Mathematics and Adventure....Pages 74-79 Passion Plays: Melodramas about Mathematics....Pages 80-87 Front Matter....Pages 89-89 A Basic Parameterized Complexity Primer....Pages 91-128 Kernelization – Preprocessing with a Guarantee....Pages 129-161 Parameterized Complexity and Subexponential-Time Computability....Pages 162-195 Fixed-Parameter Tractability of Treewidth and Pathwidth....Pages 196-227 Graph Minors and Parameterized Algorithm Design....Pages 228-256 Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey....Pages 257-286 Backdoors to Satisfaction....Pages 287-317 Studies in Computational Aspects of Voting....Pages 318-363 A Parameterized Halting Problem....Pages 364-397 Computer Science Unplugged and Related Projects in Math and Computer Science Popularization....Pages 398-456 FPT Suspects and Tough Customers: Open Problems of Downey and Fellows....Pages 457-468 What’s Next? Future Directions in Parameterized Complexity....Pages 469-496 Back Matter....Pages - Parameterized Complexity Is Currently A Thriving Field In Complexity Theory And Algorithm Design. A Significant Part Of The Success Of The Field Can Be Attributed To Michael R. Fellows. This Festschrift Published In Honor Of Mike Fellows On The Occasion Of His 60th Birthday. It Contains 20 Papers That Showcase The Important Scientific Contributions Of This Remarkable Man Describes The History Of The Field Of Parameterized Complexity, And Also Reflects On Other Parts Of Mike Fellows’s Unique And Broad Range Of Interests, Including His Work On The Popularization Of Discrete Mathematics For Young Children. The Volume Contains Several Surveys That Introduce The Reader To The Field Of Parameterized Complexity And Discuss Important Notions, Results, And Developments In This Field. Hans L. Bodlaender ... [et Al.] (eds.). Includes Curriculum Vitae Michael R. Fellows. Includes Bibliographical References And Index.