Resolving infeasibility in extremal algebras Original Research Article

Two extremal algebras script capital b=(Bcircled plus,circle times operator) based on a linearly ordered set (B, less-than-or-equals, slant) are considered: in the maxmin algebra minus sign in circle=max, circle times operator = min and in the maxgroup algebra circled plus = max and circle times operator is a group operation. If a system A circle times operator x = b of linear equations over an extremal algebra is insolvable, then any subset of equations such that its omitting leads to a solvable subsystem is called a relieving set. We show that the problem of finding the minimum cardinality relieving set is NP-complete in the maxmin algebra already for bivalent systems, while it is polynomially solvable for bivalent systems in maxgroup algebra and also NP-complete for trivalent systems.