DAG with modulo 3 restrictions
I don't know whether your problem is feasible, but here is another way to express it, in the language of linear algebra instead of the language of DAGs.

The upper bound on the path length means that each output vertex depends on at most $2^{27}$ input vertices... which is technically a constant.

Your problem is equivalent to the following:

Input: a matrix $M$, a vector $c$ 
Question: do there exist vectors $x,y$ all of whose entries are 0 or 1, such that $y=Mx+c \pmod 3$?

In your particular case, we are guaranteed that each row of $M$ has at most $2^{27}$ non-zero entries, and you're asking whether this is sufficient to make the problem feasible.  I don't know the answer to that.



Here is the equivalence between your formulation based on DAGs, and the linear algebra formulation above: we think of each non-input vertex as summing (modulo 3) the two inputs entering it, so it represents an addition (modulo 3) gate.  Suppose the two numbers on an input gate are $a,b$.  Then we can equivalently think of the input vertex as accepting a zero-or-one input variable $x$, and outputting $(b-a)x + a$ (modulo 3).  Note that $b-a$ and $a$ are known constants, so an input vertex computes an affine function of the corresponding zero-or-one input variables.  As a result, we have one zero-or-one input value per input vertex, and one output value per output vertex, and we are hoping that all the output values will be zero or one.  By unfolding the summations, we see that each output value is the sum (modulo 3) of at most $2^{27}$ expressions of the form $\alpha_i x_i + \beta_i$ where the $\alpha_i,\beta_i$ are known constants and the $x_i$ are the zero-or-one inputs.  That then leads to the reformulation I listed above.