Reducing graph transversals via edge contractions

DOI10.1016/j.jcss.2021.03.003zbMath1477.68239arXiv2005.01460MaRDI QIDQ2037191

Ignasi Sau, Uéverton S. Souza, Vinícius Fernandes dos Santos, Paloma T. Lima

Publication date: 30 June 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.01460

zbMATH Keywords

vertex cover; feedback vertex set; parameterized complexity; edge contraction; odd cycle transversal; blocker problem; graph transversal

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization