Can this Integer Linear Programming problem be solved in polynomial time?

Question

I have $n$ binary variables, and $m$ constraints. Each constraint can be stated as: "exactly $b$ of the variables in $S$ are equal to 1", for some positive integer $b$ and subset of the variables $S$. I want to know two things:

1. Can I assign a value to each variable so that every constraint is satisfied?

2. If so, how can I minimize the number of variables that equal 1?

To express this as an Integer Linear Programming (ILP) problem, we can make each variable an element of the vector $\mathbf{x} \in \{0,1\}^n$, and write the constraints as $A\mathbf{x}=\mathbf{b}$, where $A \in \{0,1\}^{m \times n}$ and $\mathbf{b} \in (\mathbb{Z}^{+})^m$. The "objective function" is $\mathbf{c}^\mathrm{T}\mathbf{x}$, where $\mathbf{c}$ is an $n$-element vector of 1s. So, the original questions are the same as:

1. Does there exist $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$?
2. Find $\mathbf{x}$ to minimize $\mathbf{c}^\mathrm{T}\mathbf{x}$ subject to $A\mathbf{x}=\mathbf{b}$.

For general ILP with binary variables, question #1 is NP-complete, and #2 is NP-hard, so there isn't a polynomial-time solution. However, in my problem, $A$'s entries are all 0 or 1, which makes me believe there should be a polynomial-time solution.

Is there a polynomial-time algorithm to solve this kind of ILP problem?

---

The closest I've gotten to an answer is to translate the problem into Minimum-Cost Maximum Flow, as follows.

We create a network $N = (V, E)$, whose nodes include a source node $s$, sink node $t$, and a node for each variable and constraint in the original problem: $$ \begin{align} V = \: &\{s, t\} \\ &\cup \{x_i \;|\; i\in\{1,2,...,n\}\} \\ &\cup \{y_j \;|\; j\in\{1,2,...,m\}\} \end{align} $$ $E$ has an edge from $s$ to each variable, from each variable to the constraints which include it, and from each constraint to $t$: $$ \begin{align} E = \: &\{(s, x_i) \;|\; i\in\{1,2,...,n\}\} \\ &\cup \{(x_i, y_j) \;|\; A_{ji} = 1\} \\ &\cup \{(y_j, t) \;|\; j\in\{1,2,...,m\}\} \end{align} $$ The capacity of each edge is: $$ \begin{align} c(s, x_i) &= \sum_{j=1}^{m} A_{ji} \\ c(x_i, y_j) &= 1 \\ c(y_j, t) &= b_j \\ \end{align} $$ Finally, the cost of each edge is: $$ \begin{align} a(s, x_i) &= 1/c(s, x_i) \\ a(x_i, y_j) &= 0 \\ a(y_j, t) &= 0 \\ \end{align} $$

Conceptually, saturating an $x_i$ node means setting the corresponding variable to 1, and saturating a $y_i$ node means satisfying the corresponding constraint. Any flow $f$ can be translated back into an assignment of binary values for $\mathbf{x}$ by setting $x_i=1$ when $f(s, x_i) = c(s, x_i)$ and $x_i=0$ when $f(s, x_i) = 0$, unless we have $0 < f(s, x_i) < c(s, x_i)$ for some $x_i$, in which case there isn't a meaningful translation.

Then, the original questions are equivalent to the following:

1. Does there exist a maximum flow $f$ whose value is $\sum_{j=1}^{m} b_j$, which also satisfies $f(s, x_i) = 0 \,\lor\, f(s, x_i) = c(s, x_i) \;\forall\; i\in\{1,2,...,n\}$?

2. If so, which of these flows has the lowest cost, $\sum_{(u, v)\in E}a(u,v)f(u,v)$?

Question #1, ignoring the condition on $f(s, x_i)$, is the decision Maximum Flow problem, which I can solve using the Ford-Fulkerson algorithm in $O(mn)$ time. Question #2 is the Minimum-Cost Flow problem, which I understand also has polynomial-time algorithms.

The problem is I can't just use the FF algorithm directly! If it gives me a flow which doesn't satisfy the condition on $f(s, x_i)$, then I can't translate the flow back into an assignment for $\mathbf{x}$.

So my follow-up question is, am I at least on the right track? Can I modify a Max Flow algorithm to only return flows which satisfy the condition on $f(s, x_i)$, while still running in polynomial time?

Answer 1

No, the problem is NP-complete, by reduction from Exact Cover, so there is not likely to be any polynomial-time algorithm (unless P=NP). Suppose you have an instance of Exact Cover, i.e., a collection $\mathcal{S}$ of sets. Introduce one binary variable $x_S$ per set $S \in \mathcal{S}$. For each element $e$ that appears in any set, consider the sets $S \in \mathcal{S}$ such that $e \in S$; we obtain a constraint that exactly 1 out of the corresponding binary variables are set to 1. In other words, the constraint is

$$\sum_S x_S = 1,$$

where the sum is over all sets $S \in \mathcal{S}$ such that $e \in S$. There exists an exact cover iff the resulting constraint system is satisfiable. Therefore, any polynomial-time algorithm to solve your type of constraints would immediately yield a polynomial-time algorithm to solve Exact Cover. But Exact Cover is already known to be NP-complete.