2
$\begingroup$

Consider the following problem.

The input is a Directed Acyclic Graph. Each vertex $v_i$ may have exactly 0 or 2 incoming edges with associated vertices $v_{i1}$ and $v_{i2}$. If it has 0 incoming edges, it is considered an input vertex. The input of the problem specifies with each input vertex exactly two numbers out of {0,1,2} that may be associated with that input vertex.

Each vertex may have any number of outgoing edges. All vertices that don't have any outgoing edge, are considered output vertices.

The goal of our algorithm is to associate with each vertex a number 0, 1 or 2 that respects the constraints:

  • each input vertex must be associated with one of its two numbers in the input.
  • each output vertex must be associated with 0 or 1.
  • each non-input vertex $v_i$ must be associated with $(v_{i1} + v_{i2}) \bmod 3$.

Example problem and solution:

DAG mod 3 example problem and solution

The general case for this problem should be NP-complete. But in my case, all paths from any input vertex to any output vertex have length at most $c$, where $c=27$. Does this make the problem feasible?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If we consider the nonzero entries as part of the input, it should be NP-complete and this would be infeasible. I'm just hoping that your formulation is more general than my original problem. It doesn't seem so, but I need to let it sink in for a while. $\endgroup$ – Albert Hendriks Mar 25 '17 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.