Tractable but Hard to Approximate: The Bi‐Objective Minimum s‐t‐Cut Problem With Binary Capacities

ABSTRACT The minimum ‐‐cut problem is one of the most‐studied problems in discrete optimization and has a unique complexity status in multi‐objective optimization. Even though the single‐objective version of the problem can be solved in polynomial time, it has been shown in the seminal work of Papadimitriou and Yannakakis (2000) that there does not exist a multi‐objective fully polynomial‐time approximation scheme (MFPTAS) for the minimum ‐‐cut problem unless . This holds both for the case of objective functions with arc capacities in and for objective functions with general capacities, and even for tractable instances where the number of non‐dominated points is only quadratic in the input size. In this article, we strengthen these results by showing that, assuming , there does not exist an MFPTAS for the minimum ‐‐cut problem with two objectives and arc capacities in , nor for the minimum ‐‐cut problem with two objectives and arc capacities in . This advancement is particularly interesting since the considered problem variants are the only known problems in multi‐objective optimization that do not admit an MFPTAS even though their single‐objective versions are solvable in polynomial time and the problems are tractable , that is, the numbers of non‐dominated points are polynomial (even linear) in the input size. Furthermore, we complement this result by showing that, on graphs of bounded tree‐width, the minimum ‐‐cut problem with polynomially bounded arc capacities can be solved exactly in polynomial time for any constant number of objectives.