Eliminar Ciclos pela Remoção de um Emparelhamento Parametrizado pela Largura em Árvore é FPT

• Carlos V. G. C. Lima UFCA
• Thiago Marcilon UFCA
• Cícero S. Morais UFCA

DOI: https://doi.org/10.5753/etc.2023.230565

Abstract

Given a graph G = (V,E), a decycling matching M ⊆ E(G) of G is a matching whose removal eliminates all the cycles of G (i.e. G − M is a forest). We study the problem of determining whether G admits a decycling matching. This problem is known to be NP-complete even for subcubic graphs. In this work we prove that it is FPT when parameterized by the treewidth.

References

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.