# Is sum-balanceability computable?

Let $$\mathbb{N}$$ denote the set of positive integers, and let $$G=(V,E)$$ be a finite simple, undirected graph. Given $$f:V\to \mathbb{Z}$$ we define the neighborhood sum function $$\mathrm{nsum}_f:V\to\mathbb{Z}$$ by setting

$$\mathrm{nsum}_f(v) = \sum\{f(w):w\in N(v)\}$$ for all $$v\in V$$.

We say that a graph $$G=(V,E)$$ is sum-balanceable if there is an injective function $$f:V\to\mathbb{Z}$$ such that $$\mathrm{nsum}_f(v) = 0$$ for all $$v\in V$$.

My goal is to prove that sum-balanceability is computable. One way to do this is to show that in order to find an injective $$f:V\to\mathbb{Z}$$ with the desired property, we only need to check finitely many combinations for assignments of $$v\in V$$ to an integer. Let's make this hand-waving formal.

Question. Is there a computable function $$b:\mathbb{N}\to\mathbb{N}$$ with the following property?

Whenever $$G=(V,E)$$ with $$|V| = n\in\mathbb{N}$$ is sum-balanceable, there is an injective function $$f:V\to \mathbb{Z}$$ with $$\mathrm{nsum}_f(v) = 0$$ for all $$v\in V$$ and $$|f(v)| \leq b(n)$$ for all $$v\in V$$.

Note that the existence of such a computable function $$b:\mathbb{N}\to\mathbb{N}$$ would directly imply that sum-balanceability is computable.

Yes, there is such a computable function $$b$$, which follows from the fact that one can compute solutions to integer programs. Note that we can model sum-balanceability by first introducing an integer variable $$x_v$$ for each vertex $$v \in V(G)$$ and writing down the $$n$$ linear equations $$\sum_{v \in N(u)} x_v=0$$ for each vertex $$u \in V(G)$$. We still have to ensure that $$x_u \neq x_v$$ for all $$u \neq v$$, but we can guess the order of the variables and add these as linear inequalities to our integer program. For example, if $$V(G)=[n]$$, then we can write $$x_n \geq x_{n-1}+1 \geq x_{n-2}+2 \geq \dots \geq x_1+n-1$$ to encode the order $$x_n> \dots > x_1$$. Thus, $$G$$ is sum-balanceable if and only if at least one of the above $$n!$$ integer programs is feasible.
In fact, it seems sum-balanceability can be decided in polynomial-time using just linear algebra as follows. Let $$A$$ be the $$V(G) \times V(G)$$ adjacency matrix of $$G$$. Note that $$G$$ is sum-balanceable if and only if there exists an integer vector $$\mathbf x \in \mathbb{Z}^{V(G)}$$ in the nullspace of $$A$$ such that all entries of $$\mathbf x$$ are distinct. To decide if $$\mathbf x$$ exists, compute a basis $$\mathbf{x}^1, \dots, \mathbf{x}^k$$ of the nullspace of $$A$$. Then $$G$$ is sum-balanceable if and only if for all distinct $$u,v \in V(G)$$, there exists $$i \in [k]$$ such that $$\mathbf{x}_{u}^{i} \neq \mathbf{x}_{v}^{i}$$.