Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

Sorry for bad English.

Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$.

But what if we can't walk through a vertex more than one times?

share|improve this question
2  
It that would be as simple as some modified $A^n$, then you would solve Hamiltonian path problem in polynomial time. Of course, we don't know whether $P = NP$ or not, but I strongly suspect, that your formula to be easily provable, will have to include (somewhere, maybe indirectly) exponential number of operations, e.g. $2^n$ additions, multiplications, assignments, whatever. – dtldarek Feb 10 at 9:36
@dtldarek: Isn't $A^n$ exponential in $n$? – Raskolnikov Feb 10 at 9:52
@Raskolnikov In terms of number of operations, no. E.g. $a^{12} = a\cdot a \cdot a \cdot \ldots \cdot a$ which uses only linear number of multiplications. Moreover, if you rearrange it smartly (that is via Horner's scheme) you can make it even logarithimc in $n$, e.g. $a^{12} = ((a^2\cdot a)^2)^2$. – dtldarek Feb 10 at 10:52
@dtldarek: Yes, but that only computes how many paths of length $n$ there are. Searching those paths for Hamiltonian ones means searching through an exponentially growing number of paths, regardless of how fast that number can be computed. – Raskolnikov Feb 10 at 11:59
@Raskolnikov An oracle that calculates the number of paths of length $|V|$ that doesn't go twice through any vertex is enough to solve Hamiltonian path problem. Moreover, even if the original problem is of the form "is there a Hamiltonian path of length $k$", it is easy to compute the path itself – just remove any unnecessary edges until a single path remains. – dtldarek Feb 10 at 15:28

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.