On Mathematical Models for the Maximum d-Cut Problem

This paper investigates the Maximum d-Cut Problem, a generalization of the classic Maximum Cut and Matching Cut problems. Given a weighted graph and a parameter d, the goal is to find a vertex partition that maximizes the total weight of edges crossing the cut, under the constraint that each vertex has at most d neighbors in the opposite partition. We present mathematical programming formulations for the problem, including quadratic and linear integer programming models, and propose a preprocessing technique based on the identification of indivisible subgraphs. This technique reduces problem size by detecting vertex subsets that must belong to the same partition in any feasible solution. We also prove a sufficient condition under which a subgraph admits a d-cut, contributing to the theoretical understanding.