Finding a graph where the edge set satisfies a set of integer equations

Question

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?

Answer 1

You are asking two questions. I will answer the first one. Your first problem is NP-hard, by reduction from exactly 1-in-3 positive 3-SAT.

Let $\varphi$ be a positive 3-CNF formula with $m$ clauses and at most $n^2$ variables $x_i$. Label each edge $(v_i,v_j)$ with a distinct variable $x_{ij}$. Each set $S_i$ will correspond to a clause of $\varphi$ as follows: the set $S_i$ contains one edge $(v_i,v_j)$ for each variable $x_{ij}$ that appears in that clause. Let $k_1=k_2=\cdots = k_m=1$.

Now the resulting system of linear equations has a solution if and only if $\varphi$ has an assignment where every clause has exactly one of its three variables set to true.