0
$\begingroup$

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.

$\endgroup$
  • $\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
2
$\begingroup$

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.

$\endgroup$
  • $\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

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.