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.
Boeckmann et al. (Thu,) studied this question.