It depends what on what bells&whistles you want, but line breaking is “theoretically” quadratic but, for most use cases, basically linear. A real misfortune is that the Knuth-Plass algorithm was published before we had a good grasp on how to present algorithms well. The actual algorithm is basically just a linear pass (reverse) along with a memo-table. (This is usually described as “dynamic programming”, but I find that term less than useless.)

https://github.com/jaroslov/knuth-plass-thoughts

Yes, but as this blog post shows, you can apply dynamic programming (and then various other optimizations) to make it fast for common uses.

Even if it is NP Complete, that would really just limit you on the size of a text for which you could find the absolute best line breaking.

Consider, the traveling salesman for the capitals of the US is easily solvable, due to the small size of the problem space. Similarly, I'd imagine the actual problem space to not be that large on line breaking.

Specifically, since line breaking is limited to the paragraphs you are looking at, this probably isn't an issue in most cases. Degenerate cases could be checked for and processing limited to not try too much.

It doesn't actually matter, unless you need an exact solution to the problem. There are often a number of relatively close and efficient solutions when "close enough" is what you're aiming for.