Crossposted at Theoretical Computer Science SE
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 the helpful comment below, 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.
