4 ms·

What makes it NP-hard? Naively, I would assume the number of simple paths between any two nodes in a graph to a polynomial function of the number of nodes plus

What makes it NP-hard? Naively, I would assume the number of simple paths between any two nodes in a graph to a polynomial function of the number of nodes plus the number of edges, so checking every path wouldn't be hard.

penteract 3y ago
In the complete graph on n vertices, there are (n-2)! simple paths of length n-1 between any pair of distinct vertices, which is more than any polynomial in the number of vertices or edges.
deleted 3y ago
[deleted]
3np 3y ago
> What makes it NP-hard? That's the question, isn't it?