Optimal 3-terminal cuts and linear programming.

Given an undirected graph G=( V, E) and three specified terminal nodes t ₁, t ₂, t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\ A. If a non-negative edge weight c _e is specified for each e∈ E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is [InlineMediaObject not available: see fulltext.]-hard, and in fact, is max-[InlineMediaObject not available: see fulltext.]-hard. An approximation algorithm having performance guarantee [InlineMediaObject not available: see fulltext.] has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most [InlineMediaObject not available: see fulltext.] times the optimal LP value. It is proved here that [InlineMediaObject not available: see fulltext.] can be improved to [InlineMediaObject not available: see fulltext.], and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee [InlineMediaObject not available: see fulltext.]. In addition, we show that [InlineMediaObject not available: see fulltext.] is best possible for this algorithm. [ABSTRACT FROM AUTHOR]