Resolving infeasibility in extremal algebras (Q1300912)

Two extremal algebras \({\mathcal B}=(B,\oplus,\otimes)\) based on a linearly ordered set \((B,\leq)\) are considered: in the maxmin algebra \(\oplus =\max\), \(\otimes=\min\), and in the maxgroup algebra \(\oplus=\max\) and \(\otimes\) is a group operation. If a system \(A\otimes 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. The paper shows 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.