First I struggled to decide where to put the navigation controller, I wanted a lot my ViewModel to decide when to go from a screen to another. I still had this impression the ViewModel should be the grand orchestrator of the UI, and so be the one to finally call navigate() on the navigation controller. I wanted to inject a wrapper of the navigation controller in the ViewModel (something like this).
But after I watched a conference on states in the UI Layer by Manuel Vivo and I dived into the Now In Android repository, I decided to change my point of view. To let the ViewModel knows only what it should know in case of configuration change, and to keep the rest in the UI components, including the navigation.
So the navigation controller stays in the NavHost component.