I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve this problem, or there is no optimal solution for that. 
The following paper mentioned this fact in its introduction:
"An exact algorithm for graph partitioning"
However, they provided an exact solution for GP using branch-and-bound algorithm. Isn't it a paradox?, I mean I assume that if a problem is NP-Complete, there is also no exact solution for that, right?



What is the difference between exactness and optimality of an algorithm?
I presume the paper you're referring to is [this one](https://arxiv.org/pdf/0912.1664.pdf) by Hager, Phan and Zhang.


There are no known polynomial-time algorithms for NP-complete problems. This is no exception. I note that at the end of Section 4 it states:



> 
> In the worst case, the branch and bound algorithm will build all $2^{n+1}-1$ nodes of the tree.
> 
> 
> 


So: this is not a polynomial-time algorithm. That does not prevent it from being useful in practice. 


