Abstract
Given a graph and a set of paths we want to cut (usually implicitly defined), cut problems ask to find the smallest number of edges of vertices that intersect all given paths. We survey recent developments on approximation algorithms and hardness of approximation (assuming the Unique Games Conjecture) for various cut problems, including Directed Multicut, Length-Bounded Cut, and their non-fixed terminal counterparts. We will highlight the efforts to find the optimal LP relaxation for each problem, and introduce a framework that converts their integrality gaps to hardness results.
Based on joint work with Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Chao Xu, and Vivek Madan.