Multivariate Investigation of NP-Hard Problems: Boundaries Between Parameterized Tractability and Intractability

  • Uéverton Souza UFF
  • Fábio Protti UFF
  • Maise da Silva UFF
  • Dieter Rautenbach Universität Ulm

Resumo


In this thesis we present a multivariate investigation of the complexity of some NP-hard problems, i.e., we first develop a systematic complexity analysis of these problems, defining its subproblems and mapping which one belongs to each side of an “imaginary boundary” between polynomial time solvability and intractability. After that, we analyze which sets of aspects of these problems are sources of their intractability, that is, subsets of aspects for which there exists an algorithm to solve the associated problem, whose non-polynomial time complexity is purely a function of those sets. Thus, we use classical and parameterized complexity in an alternate and complementary approach, to show which subproblems of the given problems are NP-hard and latter to diagnose for which sets of parameters the problems are fixed-parameter tractable, or in FPT. This thesis exhibits a classical and parameterized complexity analysis of different groups of NP-hard problems. The addressed problems are divided into four groups of distinct nature, in the context of data structures, combinatorial games, and graph theory: (I) and/or graph solution and its variants; (II) flooding-filling games; (III) problems on P3-convexity; (IV) problems on induced matchings.

Referências

R. G. Downey, M. Fellows. Parameterized complexity, Springer, 1999.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.

J. Flum, M. Grohe. Parameterized complexity theory, Springer, 2006.

R. Niedermeier. Invitation to fixed-parameter algorithms, Oxford University Press, 2006.
Publicado
20/07/2015
SOUZA, Uéverton; PROTTI, Fábio; DA SILVA, Maise; RAUTENBACH, Dieter. Multivariate Investigation of NP-Hard Problems: Boundaries Between Parameterized Tractability and Intractability. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 28. , 2015, Recife. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2015 . p. 19-24. ISSN 2763-8820. DOI: https://doi.org/10.5753/ctd.2015.9996.