Fixed-Parameter Tractability (bibtex)

by Marko Samer, Stefan Szeider

Abstract:

Parameterized complexity is a new theoretical framework that considers, in addition to the overall input size, the effects on computational complexity of a secondary measurement, the parameter. This two-dimensional viewpoint allows a fine-grained complexity analysis that takes structural properties of problem instances into account. The central notion is "fixed-parameter tractability" which refers to solvability in polynomial time for each fixed value of the parameter such that the order of the polynomial time bound is independent of the parameter. This chapter presents main concepts and recent results on the parameterized complexity of the satisfiability problem and it outlines fundamental algorithmic ideas that arise in this context. Among the parameters considered are the size of backdoor sets with respect to various tractable base classes and the treewidth of graph representations of satisfiability instances.

Reference:

Fixed-Parameter TractabilityMarko Samer, Stefan SzeiderChapter in Handbook of Satisfiability (A. Biere, M. Heule, H. van Maaren, T. Walsh, eds.), volume 185 of Frontiers in Artificial Intelligence and Applications, pages 425–454, February 2009, IOS Press.

Bibtex Entry:

@incollection{SamSze09HBSAT, author = {Marko Samer and Stefan Szeider}, title = {Fixed-Parameter Tractability}, month = {February}, year = {2009}, booktitle = {Handbook of Satisfiability}, chapter = {13}, editor = {A. Biere and M. Heule and H. van Maaren and T. Walsh}, pages = {425--454}, publisher = {IOS Press}, series = {Frontiers in Artificial Intelligence and Applications}, volume = {185}, abstract = {Parameterized complexity is a new theoretical framework that considers, in addition to the overall input size, the effects on computational complexity of a secondary measurement, the parameter. This two-dimensional viewpoint allows a fine-grained complexity analysis that takes structural properties of problem instances into account. The central notion is "fixed-parameter tractability" which refers to solvability in polynomial time for each fixed value of the parameter such that the order of the polynomial time bound is independent of the parameter. This chapter presents main concepts and recent results on the parameterized complexity of the satisfiability problem and it outlines fundamental algorithmic ideas that arise in this context. Among the parameters considered are the size of backdoor sets with respect to various tractable base classes and the treewidth of graph representations of satisfiability instances.}, isbn = {978-1-58603-929-5}, doi = {10.3233/978-1-58603-929-5-425} }

Powered by bibtexbrowser