Given a cubic graph $G$ (i.e. a graph where all nodes have degree $3$) with $N$ nodes and $M$ edges, each edge is assigned a variable $x_i$. For each node, we are given $y_i$ which is a polynomial in the three variables connected to that node. The coefficients for all the terms in the polynomials are either $0$ or $1$. Then for the graph we define the graph polynomial $F$ as the product of all the $y_i$'s. We want to determine whether the coefficient for $x_1 x_2 x_3 ... x_M$ is $0$ or $1$ (mod $2$) (once we fully expand the associated polynomial $F$).
The following figure shows an example with $N=6$ nodes and $M=9$ edges. We want to know once we fully expand $F$, whether or not the coefficient for the term $x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9$ is $1$ (mod $2$) or $0$.
What is the best way to test that? Is there any efficient algorithm available? Or is there a (relatively) easy way to prove it is NP-hard? Any help is appreciated. Is there some recursive procedure that could be used ?
As background this problem came up in my research for identifying the subset of the SAT problems with polynomial algorithm.