On this thesis we study kernels and parameterized algorithms for the FEEDBACK VERTEX SET problem for directed and undirected graphs. In this problem we want to delete at most k vertices from a graph G to make it acyclic. This problem is NP-Hard, so the research is focused on alternative ways of solving the problem (e.g. approximation algorithms, heuristics, etc.). Another way is via parameterized algorithms, and this is the scope of this thesis.
On undirected graphs there is a kernel of size O(k^2) for a general instance. On directed graphs the existence of a polynomial kernel for general instances is an open problem. On this thesis we study the case when the problem is parameterized by the FEEDBACK VERTEX SET of the corresponding undirected graph, which has kernel of size O(k^4).
The algorithms for the undirected graphs make use of combinatorial arguments to find their complexity, and there is a case which used a Python program to find the complexity of the algorithm. For directed graphs, the algorithms make use of tools from graph theory (e.g. cuts, separators) and in some cases they use some more abstract stuctures, such as ε-structures. The complexity of the algorithms for the directed feedback vertex set is based again on combinatorial arguments.
The FEEDBACK VERTEX SET is a well studied problem in Parameterized Complexity with many applications on Operational Systems, VLSI design and in the search of genes that cause cancer and it belongs to a bigger class of problems that searches for Feedback Sets. Similar is the FEEDBACK ART SET problem which we can also solve with the algorithms for the FEEDBACK VERTEX SET.