|
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? |
|||||||||||||||
|
|
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$. |
|||
|
|
