= Maximum feasible subsystem
Given finitely encoded linear inequalities, a <maximum feasible subsystem> is a largest collection that can be simultaneously satisfied. Its decision version asks whether some $k$ inequalities admit a common solution. This is <NP-complete>, despite <polynomial time> feasibility testing for each fixed collection. For a graph, use nonnegative variables $x_v$, constraints $x_v\geq1$ for vertices, and $M>|V|$ copies of $x_u+x_v\leq1$ for each edge. A subsystem of size $M|E|+k$ must retain a copy of every edge constraint and at least $k$ vertex constraints; those vertices form an <independent set>. Conversely an <independent set> of size $k$ supplies such a feasible subsystem by its indicator vector.
Back to article page
