  The minimum and maximum cuts of an undirected edge-weighted graph are classic
problems in graph theory. While the Min-Cut Problem can be solved in P, the
Max-Cut Problem is NP-Complete. Exact and heuristic methods have been developed
for solving them. For both problems, we introduce a natural extension in which
cutting an edge induces a cost. Our goal is to find a cut that minimizes the
sum of the cut weights but, at the same time, restricts its total cut cost to a
given budget. We prove that both restricted problems are NPComplete and we also
study some of its properties. Finally, we develop exact algorithms to solve
both as well as a non-exact algorithm for the min-cut case based on a
Lagreangean relaxation that generally provides optimal solutions. Their
performance is reported by an extensive computational experience.
