There is an easy and hard version of the problem I am asking about, so I will start with the easy to make for clearer reading.
Suppose that we are have a set of vertices $V =\{v_1,v_2,...,v_n\}$ and sets $S_1,S_2,...,S_m \subset V \times V$. Let
$s_{ijk} = 1$ if $\ (v_j,v_k) \in S_i $, 0 otherwise.
Given integers $\ k_1,...,k_m$ we want to find whether the set of equations
$$\begin{align*} k_1 &= \sum_{j,k} a_{jk} s_{1jk}\\ k_2 &= \sum_{j,k} a_{jk} s_{2jk}\\ &\vdots\\ k_m &= \sum_{j,k} a_{jk} s_{mjk} \end{align*}$$
has a solution with all of the $a_{11}, a_{12}, ... , a_{nn}$ indices in $\{0,1\}$.
Explanation
This set of 0-1 equations is equivalent to checking whether or not there exists a (simple directed) graph with $\ k_i$ edges from each of the subsets $\ S_i$. My immediate instinct is that this problem is solvable in polynomial time, say by a straightforward backtracking algorithm. Another possibility is to solve the system using the appropriate technique (say Hermite Normal Form) and then applying LLL to get a short basis for the solutions. The proof that this is solvable in polynomial time isn't entirely clear to me though.
Example
We are given $\ v_1, v_2, v_3.$
$\ S_1 = (v_2, v_3) $
$\ S_2 = (v_1, v_3), (v_2, v_3)$
$\ k_1 = 1, k_2 = 0$
We return false because we have to pick $\ (v_2,v_3)$ but this forces $\ k_2 > 0$ since we have to pick it in the second set as well.
The harder version:
Does there exist a (directed) graph $G$ with $\ k_i $ edges from each subset $\ S_i$ such that
$\ G = cl(G)$,
where $\ cl(G) $ denotes the transitive closure?
We can solve this by testing the feasibility of a set of 0-1 linear equations and inequalities, but as we should know that problem is NP hard in general (unlike solving linear integer equations). However it does not look at all trivial to show that this particular problem is NP hard.
Questions
Can the first problem always be solved in polynomial time?
Is the second problem NP hard?