Fixed-parameter tractability

被引：27
作者：
Samer, Marko
Szeider, Stefan
机构：
来源：
Frontiers in Artificial Intelligence and Applications | 2009年 / 185卷 / 01期
关键词：
D O I：
10.3233/978-1-58603-929-5-425
中图分类号：
学科分类号：
摘要：
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. © 2009 John Franco and John Martin and IOS Press."
引用
收藏
页码：425 / 454
页数：29
相关论文
共 78 条
  • [1] Arnborg S., Corneil D.G., Proskurowski A., Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, 8, 2, pp. 277-284, (1987)
  • [2] Aharoni R., Linial N., Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas, Journal of Combinatorial Theory, Series A, 43, 2, pp. 196-204, (1986)
  • [3] Amir E., Efficient approximations for triangulation of minimum treewidth., Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI'01), pp. 7-15, (2001)
  • [4] Bacchus F., Dalmao S., Pitassi T., Algorithms and complexity results for #SAT and Bayesian inference, Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), pp. 340-351, (2003)
  • [5] Bodlaender H.L., Fomin F.V., Koster A.M.C.A., Kratsch D., Thilikos D.M., On exact algorithms for treewidth, LNCS, 4168, pp. 672-683, (2006)
  • [6] Bodlaender H.L., Gilbert J.R., Hafsteinsson H., Kloks T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, 18, 2, pp. 238-255, (1995)
  • [7] Bodlaender H.L., Kloks T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, 21, 2, pp. 358-402, (1996)
  • [8] Bouchitte V., Kratsch D., Muller H., Todinca I., On treewidth approximations, Discrete Applied Mathematics, 136, 2-3, pp. 183-196, (2004)
  • [9] Bodlaender H.L., A tourist guide through treewidth, Acta Cybernetica, 11, 1-2, pp. 1-22, (1993)
  • [10] Bodlaender. H.L., A linear-time algorithm for finding treedecompositions of small treewidth, SIAM Journal of Computing, 25, 6, pp. 1305-1317, (1996)
12345678