Lecturer: Igor Razgon (Cork, Ireland)
| We will present a O(1.8899n) algorithm for solving the Feedback Vertex Set (FVS) problem, a well-known intractable optimization problem. This is the first algorithm solving this problem faster than O(2n). The talk consists of 3 parts.
In the first part, we will define the notion of the exact algorithm, describe a very simple algorithm for the Maximum Independent Set (MIS) problem, and provide motivation to do research in this area. In the second part, we will present the proposed algorithm for solving FVS. This algorithm computes the complement of FVS, the Maximum Induced Forest (MIF). The algorithm is based on an observation that the MIF problem can be "transformed" to a MIS problem and the latter is easy to solve faster than O(2n). We will show the process of design of the algorithm and the most interesting details of the complexity analysis. In the third part, we will present concluding remarks related to the ways of improvement of the proposed approach and its connection to the parameterized version of FVS problem. |