On the hardness of finding near-optimal multicuts in directed acyclic graphs

AbstractGiven an edge-weighted (di)graph and a list of source–sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source–sink pairs. This is also true if we remove vertices instead of arcs