Component used: Navigation
Version used: every version since 2.4.0 (latest tested version is 2.5.1)
Latest version working correctly: 2.3.5
Devices/Android versions reproduced on: Emulator API 30, Oppo CPH2251 API 30, Samsung Galaxy S21 API 31

Repro steps:
1. Define the following 3 graphs (sample project is attached to this bug report):

<?xml version="1.0" encoding="utf-8"?>
<navigation xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/level_0_graph"
app:startDestination="@id/level_0_fragment">

<fragment
android:id="@+id/level_0_fragment"
android:name="com.example.nestedpopupto.Level0Fragment"
tools:layout="@layout/fragment_level_0">

<action
android:id="@+id/to_level_1"
app:popUpTo="@id/level_0_graph"
app:destination="@id/level_1" />
</fragment>

<navigation
android:id="@+id/level_1"
app:startDestination="@id/level_1_graph">

<include app:graph="@navigation/level_1_graph" />
</navigation>

</navigation>

<?xml version="1.0" encoding="utf-8"?>
<navigation xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/level_1_graph"
app:startDestination="@id/level_1_fragment">

<fragment
android:id="@+id/level_1_fragment"
android:name="com.example.nestedpopupto.Level1Fragment"
tools:layout="@layout/fragment_level_1">

<action
android:id="@+id/to_level_2"
app:popUpTo="@id/level_1_graph"
app:destination="@id/level_2" />
</fragment>

<navigation
android:id="@+id/level_2"
app:startDestination="@id/level_2_graph">

<include app:graph="@navigation/level_2_graph" />
</navigation>

</navigation>

<navigation xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/level_2_graph"
app:startDestination="@id/level_2_fragment">

<fragment
android:id="@+id/level_2_fragment"
android:name="com.example.nestedpopupto.Level2Fragment"
tools:layout="@layout/fragment_level_2">
</fragment>

</navigation>

2. Use "to_level_1" to navigate to nested graph.
3. Use "to_level_2" action.

Result:
The action "to_level_2" will fail with the following stacktrace:

java.lang.IllegalArgumentException: No destination with ID 2131230965 is on the NavController's back stack. The current destination is Destination(com.example.nestedpopupto:id/level_2_fragment) class=com.example.nestedpopupto.Level2Fragment
at androidx.navigation.NavController.getBackStackEntry(NavController.kt:2209)
at androidx.navigation.NavController.addEntryToBackStack(NavController.kt:1918)
at androidx.navigation.NavController.addEntryToBackStack$default(NavController.kt:1813)
at androidx.navigation.NavController$navigate$4.invoke(NavController.kt:1721)
at androidx.navigation.NavController$navigate$4.invoke(NavController.kt:1719)
at androidx.navigation.NavController$NavControllerNavigatorState.push(NavController.kt:287)
at androidx.navigation.fragment.FragmentNavigator.navigate(FragmentNavigator.kt:246)
at androidx.navigation.fragment.FragmentNavigator.navigate(FragmentNavigator.kt:162)
at androidx.navigation.NavGraphNavigator.navigate(NavGraphNavigator.kt:83)
at androidx.navigation.NavGraphNavigator.navigate(NavGraphNavigator.kt:49)
at androidx.navigation.NavGraphNavigator.navigate(NavGraphNavigator.kt:83)
at androidx.navigation.NavGraphNavigator.navigate(NavGraphNavigator.kt:49)
at androidx.navigation.NavController.navigateInternal(NavController.kt:260)
at androidx.navigation.NavController.navigate(NavController.kt:1719)
at androidx.navigation.NavController.navigate(NavController.kt:1545)
at androidx.navigation.NavController.navigate(NavController.kt:1472)
at androidx.navigation.NavController.navigate(NavController.kt:1930)
at com.example.nestedpopupto.Level1Fragment.onViewCreated$lambda-0(Level1Fragment.kt:13)

The crash will NOT occur if any of the following is applied:
- the "to_level_2" action does not use "popUpTo"
- the "level_2_graph" is not wrapped with the <navigation>.

As one can see the "to_level_1" action is identical to the "to_level_2" action and is defined in an identical graph and it works correctly. It seems that the bug occurs only when navigation is performed in the graph that is included in an other graph.

In the end I would like to remind that everything works correctly with version 2.3.5 of the androidx.navigation.