Abstract: We present here a class of "monotone" integer programs that are solvable efficiently, and in polynomial time, using a minimum cut on an associated graph. The class include any integer programs where each constraint has up to two variables, monotone IP2, where the coefficients of the two variables have opposite signs. Another type of monotone integer programs has three variables per inequality constraint with two of the variables appearing with opposite signs, and a third variable, if present, appearing in one constraint only. The "third" variables must have non-negative objective coefficients for minimization problems (or negative coefficients for maximization). These monotone IP3 problems are also solvable in polynomial time. Applications that have been discovered to be polynomial time solvable under this framework include data mining, image segmentation, certain Rayleigh ratio problems and other problems all of which are polynomial time solvable.
The class of (non-monotone) IP2 integer programs where each constraint has up to two variables, all have 2-approximation algorithms, all derived in polynomial time by solving a minimum cut problem on an associated graph. Prominent NP-hard problems that can be formulated as IP2 problems include: Vertex Cover, minimum satisfiability, min 2-SAT, the max clique represented as a min node deletion problem, several submodular minimization problem (also on multi-sets) and others. Non-monotone IP3 problems have a polynomial time algorithm to generate super optimal half integral solution which, if can be rounded to a feasible solution, generate 2-approximate solutions.