Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

New answers tagged

1

The above answer considers the version of this problem where vertices cannot be visited multiple times. However it seems that the intention of the question is that vertices could be visited multiple times. The number of such paths can be exponential in |V| and |E|, so they cannot be listed in polynomial time. The problem of counting the number of such ...


3

This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero. This problem is actually #P-hard wich is believed to be strictly harder than NP. The version of the problem where you only look for the existence of such a path is called the longest path ...


Top 50 recent answers are included