Extended cuts

Given a directed graph (Formula presented.) , three positive integers (Formula presented.) , (Formula presented.) and (Formula presented.) , and a partition (Formula presented.) of (Formula presented.) such that there are no arcs from (Formula presented.) to (Formula presented.) when (Formula presented.) or (Formula presented.) , the set of direct arcs from (Formula presented.) to (Formula presented.) , (Formula presented.) , is called an (Formula presented.) -extended cut. Given a weight vector (Formula presented.) , we aim to compute a minimum-weight (Formula presented.) -extended cut. Some special vertices may be required to belong to a particular subset (Formula presented.). We study this problem, and for special cases we provide polynomial-time algorithms, linear formulations and polyhedral descriptions. We also review some NP-hard variants.