Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

We know that counting the number of Hamiltonian paths is in $\#\mathsf{P}$.

So, what complexity (counting version) class would the counting the number of Hamiltonian paths that have two or three particular vertexes in a graph be in?

Also, what would be like if counting the number of hampaths that have two or three particular vertexes in particular place - so, for example, calculating the hampath that has vertex 3 as the second place from starting point and so on?

share|improve this question

migrated from cstheory.stackexchange.com Nov 25 '12 at 18:13

This question came from our site for theoretical computer scientists and researchers in related fields.

5  
I don't understand. A Hamiltonian path has all vertices. So what does it mean to ask about paths that have some fixed vertices. –  Suresh Oct 25 '12 at 6:03
    
no, i didn't say that the number of hampath is set; what i said was that there are two or three particular vertexes that hampath needs to have. –  rrut Oct 25 '12 at 6:48
7  
but a hampath has every vertex ! What does it mean to require it to have some particular ones. –  Suresh Oct 25 '12 at 9:16
3  
@rrut: Can you give an example of a Hamiltonian path that doesn't have a particular vertex in it? –  GManNickG Oct 25 '12 at 22:52

1 Answer 1

Just an extended comment on the second part of the question (if I understood it correctly).

The problem is a special case of the general version; so if you allow $0$ "fixed" points (a fixed point is a point that must be in a particular position in the Hamiltonian paths), then there is an immediate reduction from the problem of counting Hamiltonian paths.

If your problem says that at least $k$ points must be fixed, then this reduction should work: given a graph $G$ and two vertices $s$ and $t$, and $e_1,e_2,...,e_m$ are the edges from $s$; then for each $e_i$ split it in $k+1$ pieces adding $k$ nodes, and solve your problem fixing the first $k$ nodes (and the number returned will be equal to the number of Hamiltonian paths from $s$ to $t$ in $G$ that start with $e_i$).

At the end the total number of Hamiltonian paths in the original $G$ is the sum of the number Hamiltonian paths returned by your algorithm fixing the first $k$ points in the splitted $e_1, e_2, ... e_m$.

share|improve this answer

Your Answer

 
discard

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