I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.

I saw this question: Number of cycles in a graph? they mention the reduction from HAM #CYCLE in Counting Complexity by Arora and Barak, but I don't understand how does that help.

You have some directed graph, no one said it has a hamilton cycle, and the gadget doesn't return how many cycles there in the graph or a way to distinguish between them, it just makes all the cycles longer.

So instead, is it possible to use a topological sort to count cycles? since it can detect every cycle, we can use it to distinguish between them.

  • $\begingroup$ I'm not sure you understand what #P is. I suggest checking out the definition. $\endgroup$ – Yuval Filmus May 13 '17 at 18:42
  • $\begingroup$ I have the definition in front of me: The class of functions $f:\{0,1\}^* \to\{0,1\}^*$ that have a poly time TM M, polynom p such that $\forall x \in \{0,1\}^*$ $f(x)=|\{y∈\{0,1\}^{p(|x|)} .M(x,y)=1\}|$, I don't see how does that help in proving a problem is in #P. $\endgroup$ – shinzou May 13 '17 at 18:55
  • $\begingroup$ It's too bad they didn't give any example in class. $\endgroup$ – Yuval Filmus May 13 '17 at 18:56
  • $\begingroup$ They didn't, and I can't find any example online, closest example I found just said: "it's easy to see that #SAT is in #P"... @YuvalFilmus $\endgroup$ – shinzou May 13 '17 at 18:58

The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying $$ f(x) = |\{ |y| < p(|x|) : R(x,y) \}|. $$ In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.

  • $\begingroup$ That's it? no need to describe a way to represent a unique cycle as a witness? $\endgroup$ – shinzou May 13 '17 at 18:48
  • $\begingroup$ I did mention twice that you have to be careful. Since it's your exercise rather than mine, I won't be posting a complete solution. $\endgroup$ – Yuval Filmus May 13 '17 at 18:52
  • $\begingroup$ What's left is finding a bijection between the cycles and binary strings? $\endgroup$ – shinzou May 14 '17 at 17:27
  • $\begingroup$ Yes, this is what remains to be done. $\endgroup$ – Yuval Filmus May 14 '17 at 17:37
  • $\begingroup$ Is a topological sort that returns the paths of the cycles it finds as binary strings such that each bit is a vertex, a bijection? $\endgroup$ – shinzou May 14 '17 at 17:39

Your Answer

