5
$\begingroup$

In a MO question basically I asked when the Tutte polynomial of planar graph can be uniquely determined by the polynomially computable values at the special points and at the two hyperbolas. The solution is the unique solution of certain integer program $L$. Possibly misleading experimental data suggests this is possible sometimes.

Computing the Tutte polynomial at non-trivial points is $\#P$-complete. In case the integer program $L$ has unique solution, one call to a $NP$-complete oracle would solve $\#P$-complete problem.

In case this happens, what are the complexity implications for the subclass of planar graphs satisfying this?

Suppose the integer program $L$ has polynomially many solutions corresponding to polynomials $F_{G,i}(x,y)$. (The experimental data suggest this).

Given $G$ and a set of polynomials $F_{G,i}$ with the promise that one of them is the Tutte polynomial, what is the complexity of finding the Tutte polynomial?

AFAICT it is not harder than $\#P$ since we can compute the Tutte polynomial at positive random $(x_i,y_i)$ and see which of $F_{G,i}$ agree with the value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.