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).