Solving the Feedback Vertex Set Problem on Undirected Graphs

In this paper we propose a branch-and-cut algorithm for the exact solution of an integer multicommodity flow problem. This NP-hard problem finds important applications in transportation, VLSI design, and telecommunications. We consider alternative formulations of the problem and describe several classes of valid inequalities. We describe lifting procedures to extend a given valid inequality for the problem with k commodities, to that having a larger number of commodities. We introduce a new large class of valid constraints, the multi-handle comb inequalities. The polyhedral structure of the integer multicommodity polytope is studied in the case of unit edge capacities. We prove that this polytope is full dimensional and show that some multi-handle comb inequalities are facet defining. Also, the lifting procedures are facet preserving under certain conditions. A branch-and-cut algorithm for the exact solution of the problem is then outlined, and separation algorithms for the main classes of inequalities studied in the paper are proposed. Computational results on several classes of test problems are finally reported, with a comparison between two different formulations.