A Branch and Cut Approach to the Feedback Vertex Set Problem
Hicks, Illya V
Master of Arts
In this thesis, I use a branch and cut implementation to solve the feedback vertex set problem and add new facet defining inequalities to the literature. Feedback in a system arises when repeated traversal over some cycle causes unwanted growth or decay in the data. This can cause problems in many systems such as excess noise at a concert or deadlock forming cyclical dependence on processes in a group. To eliminate the feedback, I implement a branch and cut algorithm to make the calculations, selecting inequalities based on results from the literature. I report improvements upon previous branch and cut work in a collection of random cases. Along with this implementation, I show that the clique inequalities, which are known to be valid for the feedback vertex problem, are in fact facet inducing for all maximal clique subgraphs of the original network.
Branch and Cut; Feedback Vertex Set; Graph Theory; Combinatorial Optimization; Facet