multicut

Multicut refers to a class of problems in graph theory where the goal is to find a minimum cost set of edges that disconnect a specified set of vertices. Typically, the problem involves separating terminals (a subset of vertices) from each other. A common variation is the multicut problem on undirected graphs, where we seek a minimum weight set of edges whose removal separates each pair of vertices in a given terminal set. This contrasts with the related minimum cut problem, which aims to separate just two specific vertices or a vertex from a set.

The multicut problem is known to be NP-hard in general graphs. However, efficient algorithms exist for specific graph classes, such as planar graphs. For general graphs, approximation algorithms have been developed that can find a solution within a certain factor of the optimal cost. These algorithms often employ techniques like linear programming relaxations or randomized rounding. The complexity and solution approaches for multicut depend heavily on the underlying graph structure and the specific requirements of the separation. Applications of multicut can be found in areas like network design, where it's used to determine cost-effective ways to partition network components, and in computational biology for analyzing gene regulatory networks.