Is sum-balanceability computable?

Question

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.

Answer 1

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}$.