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.

The 3-decomposition conjecture is wide open. It asserts that every finite connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching. We prove that the following graphs are reducible configurations for the 3-decomposition conjecture: the triangle, the K2,3, the claw-square, the twin-house, and the domino. As an application, we show that all 3-connected cubic graphs of path-width at most 4 satisfy the 3-decomposition conjecture.