A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form.
$$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in \mathbb{R}$, $S$ is the set of all boolean variables, and $S$ is the set of all terms in the polynomial.
The co-occurrence graph is defined as follows.
If a pseudo-Boolean function $f:\mathbb{B}^n \mapsto \mathbb{R}$ is given by its unique multi-linear polynomial, a graph $G_f = \left(V, E\right)$ is called its co-occurrence graph, in which $\left(i, j\right) \in E$ (for $i, j \in V, i \ne j$) iff $f$ has a term for which $S \supseteq \left\{i, j\right\}$ and $c_S \ne 0$.
The tree-width of $f$ is defined as the tree-width of $G_f$.
We know that in general it is NP-hard to determine the tree-width.
My question:
What do we know about the complexity of determining the tree-width when the pseudo-Boolean function is quadratic?
It is NP-hard (NP-complete in the yes/no answer version), here is a complete proof of it : (you will see that the problems are very very close)
Initial problem : Given a graph $G=(V,E)$ and $k \in \mathbb{N}$, is the tree-width of $G$ smaller than $k$?
New problem : Given a quadratic pseudo-boolean function $f$ and $k \in \mathbb{N}$, is the tree-width of $f$ smaller than $k$?
Given a graph $G=(V,E)$ where $V=(x_1,...,x_n)$ and $k \in \mathbb{N}$, I can write in polynomial time the quadratic pseudo-boolean function $f(x_1,...,x_n) = \sum_{(i,j) \in E}x_ix_j$, and define an instance of the new problem
Is the tree-width of $f$ smaller than smaller than $k$?
Both problems obviously have the same answer, so the old problem is easier than the new which is NP-hard. Since the new one is in NP, it is NP-complete.