An Introduction to Parameterized Complexity with Applications in Algorithmic Decision Theory

摘要

The main motivation for parameterized complexity is that in many applied settings, the difficulty of solving a problem does not merely depend on the size of the instance, but on other parameters of the instance as well. It enables a much more fine-grained complexity analysis than the classical theory around NP-hardness. In this talk, we will see some of the basic algorithmic techniques for taking advantage of small parameters of the input and briefly discuss fixed-parameter intractability. The concepts will be illustrated with studies of computational problems in game theory, combinatorial game theory, voting, resource allocation, and matching markets.