3
$\begingroup$

Confusion is likely. Appears to me two papers give contradicting claims about the complexity of counting MAXCUT in planar graphs.

Exact Max 2-SAT: Easier and Faster p. 6

However, counting the number of Max 2-Sat or Max Cut solutions are $\#P$-complete even when restricted to planar graphs (results not explicitly stated but follow readily from results and reductions in [13, 20]).

[13] H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns, The complexity of planar counting problems, SIAM Journal of Computing 27 (1998), no. 4, 1142–1167.

[20] S. P. Vadhan, The complexity of counting in sparse, regular, and planar graphs, SIAM Journal of Computing 31 (2002), no. 2, 398–427.

Exponential Time Complexity of the Permanent and the Tutte Polynomial p. 13

Proposition 4.1. If #ETH holds, the coefficients of the polynomial w → Z(G; 2, w) for a given simple graph G cannot be computed in time exp(o(m)). Proof. The reduction is from #MaxCut and well-known ...Now, the coefficient of $(1 + w)^{m-c}$ in $Z(G; 2, w)$ is the number of cuts in $G$ of size $c$.

The Tutte polynomial on the hyperbola $(x-1)(y-1)=2$ is polynomially computable on planar graphs and (4) on the same page gives $Z(G;2,w)$ in terms of the Tutte polynomial on the hyperbola.

The first paper doesn't define MAXCUT, but assuming the usual definition, the two papers imply $P=\#P$.

What is wrong with this?

$\endgroup$
5
$\begingroup$

There was some discussion about this claim at the Dagstuhl seminar on Computational Counting in 2013. The technique you give to calculate #MAX-CUT is correct and it is not obvious how the hardness result is meant to "follow readily" from the two papers referenced, so I think it should be assumed that the claim of #P-hardness is in error.

I e-mailed Martin Fürer about this shortly after the seminar, and received no response.

$\endgroup$
  • $\begingroup$ Thanks. I emailed the authors of the first paper yesterday. $\endgroup$ – joro Feb 2 '16 at 9:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.