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

Project: platform/frameworks/support
Branch: androidx-master-dev

commit 781d0178da33d84f615b409b17975c8ba290401c
Author: Ian Lake <ilake@google.com>
Date:   Mon Feb 25 15:38:23 2019

    Fix navigateUp() logic when on another app's task
   
    When using deep linking on another app's task,
    only the final destination is created, ensuring that
    hitting the system back button goes back to the
    other app. The Up button, via navigateUp(), should
    take users to your own task on the parent destination.
   
    Recent changes made it so that we always add the
    parent NavGraphs to the back stack, meaning the simple
    check of back stack size == 1 does not properly handle
    this change in behavior so instead we need to check for
    the number of non-NavGraph destinations on the back
    stack.
   
    Test: new NavControllerActivityTest
    BUG: 126082008
    Change-Id: I7bf18d38e1cdd3818e7414ba44d84df0abd81b88

M       navigation/runtime/src/androidTest/AndroidManifest.xml
A       navigation/runtime/src/androidTest/java/androidx/navigation/NavControllerActivityTest.kt
M       navigation/runtime/src/main/java/androidx/navigation/NavController.java

https://android-review.googlesource.com/912258
https://goto.google.com/android-sha1/781d0178da33d84f615b409b17975c8ba290401c

A fix will be available in Navigation 1.0.0-rc02. Thanks for reporting it and the great sample app!