6 papers
Computing fixed point free automorphisms of graphs
Aida Abiad, Gabriel Coutinho, Emanuel Juliano +2
In 1981, Lubiw proved that the fixed point free automorphism problem (FPFAut) is NP-complete: given a graph G, determine whether there exists an automorphism that maps no vertex of…
Enumeration kernels for Vertex Cover and Feedback Vertex Set
Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos +1
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creig…
Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
F. Botler, Y. S. Couto, C. G. Fernandes +4
Chernyshev, Rauch, and Rautenbach proved that every connected graph on vertices with less than edges has a vertex cut that induces a forest, and co…
Exploring subgraph complementation to bounded degree graphs
Ivo Koch, Nina Pardal, Vinicius F. dos Santos
Graph modification problems are computational tasks where the goal is to change an input graph using operations from a fixed set, in order to make the resulting graph satisfy a…
Complexity of Deciding the Equality of Matching Numbers
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and…
Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins +1
A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matc…