The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to (bipartite or maximum degree 3) planar graphs.
A paper p. 12 gives some special (algebraic) points where it can be polynomially computable.
Another paper shows for planar graphs it can be polynomially computed at special points and the two hyperbolas $H_1(x,y)=0,H_2(x,y)=0, H_q(x,y)=(x-1)(y-1)-q$.
Univariate polynomial of degree $d$ can be found from $d+1$ pairs $(x_i,f(x_i))$, but the bivariate case is more complicated.
Assume the graph $G$ is planar and possibly bipartite or maximum degree $3$. Let the Tutte polynomial be $T_G(x,y)$.
Having in mind the positivity constraint, I tried to find $T_G(x,y)$ from $(x_i,y_i,T_G(x_i,y_i))$ where $(x_i,y_i)$ are the few special points and points on $H_1,H_2$.
Chose the degree $d$, for unknowns $c_{i,j}$ write $F_G(x,y)=\sum_{i,j} c_{i,j}x^iy^j$ and equate $F_G(x_i,y_i)=T_G(x_i,y_i)$. Add the constraints $c_{i,j} \ge 0$ and for the algebraic special points work over a number field, equating the algebraic integers. Make the equations integral by scaling.
We get an integer program $L$ which has at least one solution $T_G(x,y)$.
If the solution is unique (it need not be) we have found the Tutte polynomial with one call to $NP$-complete oracle, which appears nontrivial result to me.
The non-negativity constraint appears very important, since over $\mathbb{Z}$ the matrix is low rank because of the structure from the hyperbolas (I suspect if $(x_i,y_i)$ were random it would have worked even over $\mathbb{Z}$).
Q1 What is the probability $L$ has unique solution?
Q2 Does some constraint on the planar graph guarantee unique solution?
Experimental results which might be misleading
and assuming the integrity of the isl solver.
Graphs are connected planar, non-trees. A graph is bad if the solution is not unique.
On $8$ vertices: bipartite $135$, bad $8$
On $8$ vertices: maximum degree $3$ all $177$ bad $3$
On $9$ vertices: bipartite $535$ bad $100$
On $9$ vertices: maximum degree $3$ all $496$ bad $46$
Some remarks. $H_2$ is $\#P$ hard on general graphs and is closely related to counting CUTS.
On $H_1$ there is very simple closed form for $T_G$.
On $H_2$ there is no simple closed form for $T_G$.
A paper defines thickening of $G$ which is multigraph $G'$ with each edge of $G$ replaced by $k$ parallel edges.
$T_G$ and $T_G'$ are related: $T_G'(x,y)=T_G(f(x,y),g(x,y))$ and this gives more interpolation points.
Unless I am mistaken, this doesn't help for more interpolation points, since $H_2$ stays the same.
