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

The minimum 𝑠-𝑡-cut problem is one of the most-studied problems in discrete optimization and has a unique complexity statusin multi-objective optimization. Even though the single-objective version of the problem can be solved in polynomial time, ithas been shown in the seminal work of Papadimitriou and Yannakakis (2000) that there does not exist a multi-objective fullypolynomial-time approximation scheme (MFPTAS) for the minimum 𝑠-𝑡-cut problem unless $P = N P$. This holds both for thecase of 𝑝 ≥ 3 objective functions with arc capacities in {0, 1} and for 𝑝 = 2 objective functions with general capacities, and even fortractable instances where the number of non-dominated points is only quadratic in the input size. In this article, we strengthenthese results by showing that, assuming $P ≠ N P$, there does not exist an MFPTAS for the minimum 𝑠-𝑡-cut problem with twoobjectives and arc capacities in {(1, 0), (0, 1)}, nor for the minimum 𝑠-𝑡-cut problem with two objectives and arc capacities in{(0, 1), (1, 1)}. This advancement is particularly interesting since the considered problem variants are the only known problems inmulti-objective optimization that do not admit an MFPTAS even though their single-objective versions are solvable in polynomialtime 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 withpolynomially bounded arc capacities can be solved exactly in polynomial time for any constant number of objectives.