Crossposted at MathOverflow

A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is the $m$-dimensional vector with all its coordinates being 1. The nature of the problem I study guarantees that there exists at least a solution $\mathbf{x}\in[0,1]^n$ for this system, which means that the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is nonempty. I want to know what condition guarantees the existence of a 0-1 solution $\mathbf{x}\in\{0,1\}^n$ to this system.

I know that the unimodularity of $A$ is a sufficient condition, which has been useful for me. I also know the TDI condition in integer programming is sufficient, whereas I do not know how to make use of this condition. Both unimodularity and TDI guarantee that all vertices of polyhedron $P$ to be integral, thus I know there is at least a 0-1 solution (vertex), since the polyhedron is nonempty. However, all vertices being integral is more than I want, because I only care about whether there exists an integral vertex. I wonder whether there are more specialized results for this problem.

As pointed out by a helpful comment in MathOverflow, this problem is essentially equivalent to the EXACT SET COVER problem. I would now ask whether there is any condition or structure that guarantees the existence of an exact cover.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.