Take the 2-minute tour ×
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.

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 '13 at 9:36
    
@dtldarek: Isn't $A^n$ exponential in $n$? –  Raskolnikov Feb 10 '13 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 '13 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 '13 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 '13 at 15:28

1 Answer 1

Let $A\otimes B$ be defined as the product of matrices where you removed the diagonal i.e.: $$A\otimes B=(A-diag(A))\times(B-diag(B))$$ Let $A_1=A$ and $A_n=A\otimes A_{n-1}$.

The number of paths of the length n without going through a vertex more than one times is equal to the sum of elements of $A_n$.

share|improve this answer

Your Answer

 
discard

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

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