IssueTracker

One more detail here.
The body of navigateUp() method of NavController class (1.0.0-rc01) looks like this:

if (mBackStack.size() == 1) {
    // If there's only one entry, then we've deep linked into a specific destination
    // on another task so we need to find the parent and start our task from there
    ...        
} else {
    return popBackStack();
}

If I put a breakpoint on the very first line of that code and invoke this method anyhow, I can see that the size of mBackStack is actually 2 (with both root and child fragments).
So, the code doesn't consider the current case a deeplink case, but as a regular opening of the child destination.

I described this issue earlier, in https://issuetracker.google.com/issues/126014176

Partially agree, but my case doesn't use nested graphs at all, so my issue is just simpler.
However, the actual problem seems to be the same: the library treats absence of Intent.FLAG_ACTIVITY_NEW_TASK as it is actually set, because all 'start destinations' are still added before the actual deeplink destination (as it is explained in the documentation where the flag is set).

This is a regression caused by https://android-review.googlesource.com/833717 where the NavGraph destinations would always be added to the back stack (it isn't both the root and child fragments, but the root graph and the child fragment) to avoid IllegalArgumentExceptions. Unfortunately, that broke the navigateUp() behavior, which is something we'll fix :)