Eliminating All Cycles by Removing a Matching

Speaker: Carlos Vinícius G. C. Lima, Postdoc at UFF.

Date: 31 mai 2017, 13h.

Place: Room 407, Bloco H, Gragoatá, UFF.

Abstract: The problem of destroying all cycles by removing vertices or edges is classical in the literature. However, despite the large number of different works on this theme, yet there remains quite a wide field to be explored in the study of this problem when restrictions on the set of removed vertices or edges are required. We study the problem of destroying all cycles by removing a matching. We show that it is NP-complete determining whether a graph admits such a removal even for subcubic graphs with exactly two vertices of degree two. We also present polynomial time algorithms for some classical classes, that are (claw, paw)-free graphs, P_5-free graphs, chordal graphs, and C_4-free distance hereditary graphs.

Obs.: Joint Work with Uéverton S. Souza (UFF) and Dieter Rautenbach (Ulm University). The speaker is currently a Postdoc at IME-UFF, in a project coordinated by Simone Dantas (UFF).