In this chapter, we present 2-approximation algorithms for three “cut” problems: the triangle cover problem, the feedback vertex set problem on bipartite tournaments, and the node multiway cut problem. All the algorithms are based on iterative rounding but require an additional step: As usual the algorithms will pick variables with large fractional values and compute a new optimal fractional solution iteratively, but unlike previous problems we do not show that an optimal extreme point solution must have a variable with large fractional value. Instead, when every variable in an optimal fractional solution has a small fractional value, we will use the complementary slackness conditions to show that there are some special structures that can be exploited to finish rounding the fractional solution. These algorithms do not use the properties of extreme point solutions, but we will need the complementary slackness conditions stated in Section 2.1.4. The results in this chapter illustrate an interesting variant and the flexibility of the iterative rounding method.

Triangle cover

Given an undirected graph with weights on the edges, the triangle cover problem is to find a subset of edges F with minimum total weight that intersects all the triangles (3-cycles) of the graph (i.e., G – F is triangle-free).

Linear programming relaxation

The following is a simple linear programming formulation for the triangle cover problem, denoted by LPtri(G), in which xe is a variable for edge e and we is the weight of edge e.