3
$\begingroup$

It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic number of a graph through the permanent?

$\endgroup$
  • 5
    $\begingroup$ Since you can reduce #3SAt to the permanent, you can solve the permanent to find the number of solutions to the 3SAt instance. if it's more than zero, the problem is satisfiable. $\endgroup$ – Suresh Venkat Mar 11 '12 at 10:25
  • $\begingroup$ @SureshVenkat that is true. I was thinking of something else.. along the lines of given a graph using a single calculation of permanent to find the max indep number. Was curious if such a trick existed! $\endgroup$ – v s Mar 11 '12 at 19:28
  • 2
    $\begingroup$ If you want a really transparent example, the permanent of the biadjacency matrix of a bipartite graph counts the number of perfect matchings in this graph. For a non-bipartite graph, the permanent of its adjacency matrix counts the number of cycle covers. $\endgroup$ – Bruno Mar 12 '12 at 7:57
3
$\begingroup$

Here is a hint for your question in the comment to the question. The independence number of a graph can be computed by a polynomial-time oracle Turing machine which calls the #P oracle just once. That is, the independence number is in class FP#P[1].

For a graph G on n vertices, let gk(G) be the number of independent sets of size k in G. Note that 0≤gk(G)<2n. Let

$$f(G)=\sum_{k=0}^n 2^{nk}g_k(G).$$

I leave the rest of the proof as exercise.

  1. Show that function f is in #P.
  2. Show that the independence number of G can be computed from two integers n and f(G) in time polynomial in n, and conclude that the independence number can be computed in FP#P[1].
  3. (If this is not clear from item 2,) conclude that the independence number can be computed by a polynomial-time oracle Turing machine which calls the oracle for the permanent just once.

The same idea works also for the chromatic number.

$\endgroup$
  • $\begingroup$ I think this is what I may be looking for. I am unfamiliar with #P proofs. There has to be a way to show $1$ can be found through permanent of an appropriately constructed matrix. That matrix and its construction is probably what I am seeking? $\endgroup$ – v s Mar 12 '12 at 0:39
  • 1
    $\begingroup$ @vs: As I suggested in this answer, you should forget about the permanent and just use the definition of #P until step 3. Once you have a proof, you can rewrite the whole proof to use the permanent throughout the proof, but that is not intuitive because the proof of the #P-completeness of the permanent is unintuitive. $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 11:22

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.