The average running time tends to be quite good: https://imgur.com/a/Y3ZncUO http://www.dcs.gla.ac.uk/~pat/cpM/papers/gent96constrainedne... but there are pathological cases which can be extremely taxing to compute. These are at the boundary of solvable and non solvable.