Eliminar Ciclos pela Remoção de um Emparelhamento Parametrizado pela Largura em Árvore é FPT
Resumo
Dado um grafo G = (V,E), um emparelhamento deciclante M ⊆ E(G) de G é um emparelhamento cuja remoção elimina todos os ciclos de G (i.e. G − M é uma floresta). Estudamos o problema de determinar se G admite um emparelhamento deciclante. Já é conhecido que este problema é NPcompleto mesmo para grafos subcúbicos. Neste trabalho mostramos que ele está em FPT quando parametrizado pela largura em árvore.
Referências
Bondy, J. A. and Murty, U. S. R. (2008). Graph theory, volume 244 of Graduate Texts in Mathematics. Springer-Verlag London.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.
Fomin, F. V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019). Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Kloks, T. (1994). Treewidth: computations and approximations. Springer.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2017). Decycling with a matching. Information Processing Letters, 124:26–29.
Protti, F. and Souza, U. S. (2018). Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs. Discrete Mathematics & Theoretical Computer Science, vol. 20 no. 2.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.
Fomin, F. V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019). Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Kloks, T. (1994). Treewidth: computations and approximations. Springer.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2017). Decycling with a matching. Information Processing Letters, 124:26–29.
Protti, F. and Souza, U. S. (2018). Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs. Discrete Mathematics & Theoretical Computer Science, vol. 20 no. 2.
Publicado
06/08/2023
Como Citar
LIMA, Carlos V. G. C.; MARCILON, Thiago; MORAIS, Cícero S..
Eliminar Ciclos pela Remoção de um Emparelhamento Parametrizado pela Largura em Árvore é FPT. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 84-88.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230565.
