diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index 9a07dd2..105868f 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -43,7 +43,6 @@
       Consumer<DexCallSite> callSiteConsumer) {
     WorkList<DexType> workList = WorkList.newIdentityWorkList();
     workList.addIfNotSeen(type);
-    workList.addIfNotSeen(allImmediateSubtypes(type));
     while (workList.hasNext()) {
       DexType subType = workList.next();
       DexProgramClass clazz = definitionForProgramType(subType);
diff --git a/src/main/java/com/android/tools/r8/graph/LookupCompletenessHelper.java b/src/main/java/com/android/tools/r8/graph/LookupCompletenessHelper.java
new file mode 100644
index 0000000..bfc0eb4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/LookupCompletenessHelper.java
@@ -0,0 +1,67 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.graph;
+
+import com.android.tools.r8.graph.LookupResult.LookupResultSuccess.LookupResultCollectionState;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
+import java.util.Set;
+
+public class LookupCompletenessHelper {
+
+  private final PinnedPredicate pinnedPredicate;
+
+  private Set<DexType> pinnedInstantiations;
+
+  LookupCompletenessHelper(PinnedPredicate pinnedPredicate) {
+    this.pinnedPredicate = pinnedPredicate;
+  }
+
+  void checkClass(DexClass clazz) {
+    if (pinnedPredicate.isPinned(clazz.type)) {
+      if (pinnedInstantiations == null) {
+        pinnedInstantiations = Sets.newIdentityHashSet();
+      }
+      pinnedInstantiations.add(clazz.type);
+    }
+  }
+
+  LookupResultCollectionState computeCollectionState(
+      DexMethod method, AppView<? extends AppInfoWithClassHierarchy> appView) {
+    assert pinnedInstantiations == null || !pinnedInstantiations.isEmpty();
+    if (pinnedInstantiations == null) {
+      return LookupResultCollectionState.Complete;
+    }
+    WorkList<DexType> workList = WorkList.newIdentityWorkList(pinnedInstantiations);
+    while (workList.hasNext()) {
+      if (isMethodKeptInSuperTypeOrIsLibrary(workList, method, appView)) {
+        return LookupResultCollectionState.Incomplete;
+      }
+    }
+    return LookupResultCollectionState.Complete;
+  }
+
+  private boolean isMethodKeptInSuperTypeOrIsLibrary(
+      WorkList<DexType> workList,
+      DexMethod method,
+      AppView<? extends AppInfoWithClassHierarchy> appView) {
+    while (workList.hasNext()) {
+      DexClass parent = appView.definitionFor(workList.next());
+      if (parent == null) {
+        continue;
+      }
+      DexEncodedMethod methodInClass = parent.lookupVirtualMethod(method);
+      if (methodInClass != null
+          && (parent.isNotProgramClass() || pinnedPredicate.isPinned(methodInClass.method))) {
+        return true;
+      }
+      if (parent.superType != null) {
+        workList.addIfNotSeen(parent.superType);
+      }
+      workList.addIfNotSeen(parent.interfaces.values);
+    }
+    return false;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/LookupResult.java b/src/main/java/com/android/tools/r8/graph/LookupResult.java
index 7a923de..fd71a8d 100644
--- a/src/main/java/com/android/tools/r8/graph/LookupResult.java
+++ b/src/main/java/com/android/tools/r8/graph/LookupResult.java
@@ -75,6 +75,10 @@
       return state == LookupResultCollectionState.Incomplete;
     }
 
+    public boolean isComplete() {
+      return state == LookupResultCollectionState.Complete;
+    }
+
     public enum LookupResultCollectionState {
       Complete,
       Incomplete,
diff --git a/src/main/java/com/android/tools/r8/graph/PinnedPredicate.java b/src/main/java/com/android/tools/r8/graph/PinnedPredicate.java
new file mode 100644
index 0000000..d81becc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/PinnedPredicate.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.graph;
+
+@FunctionalInterface
+public interface PinnedPredicate {
+
+  boolean isPinned(DexReference reference);
+}
diff --git a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
index 4d2306c..bb10b76 100644
--- a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
@@ -81,11 +81,14 @@
   public abstract LookupResult lookupVirtualDispatchTargets(
       DexProgramClass context,
       AppView<? extends AppInfoWithClassHierarchy> appView,
-      InstantiatedSubTypeInfo instantiatedInfo);
+      InstantiatedSubTypeInfo instantiatedInfo,
+      PinnedPredicate pinnedPredicate);
 
   public final LookupResult lookupVirtualDispatchTargets(
       DexProgramClass context, AppView<AppInfoWithLiveness> appView) {
-    return lookupVirtualDispatchTargets(context, appView, appView.appInfo());
+    AppInfoWithLiveness appInfoWithLiveness = appView.appInfo();
+    return lookupVirtualDispatchTargets(
+        context, appView, appInfoWithLiveness, appInfoWithLiveness::isPinned);
   }
 
   public abstract DexClassAndMethod lookupVirtualDispatchTarget(
@@ -331,7 +334,8 @@
     public LookupResult lookupVirtualDispatchTargets(
         DexProgramClass context,
         AppView<? extends AppInfoWithClassHierarchy> appView,
-        InstantiatedSubTypeInfo instantiatedInfo) {
+        InstantiatedSubTypeInfo instantiatedInfo,
+        PinnedPredicate pinnedPredicate) {
       // Check that the initial resolution holder is accessible from the context.
       assert appView.isSubtype(initialResolutionHolder.type, resolvedHolder.type).isTrue()
           : initialResolutionHolder.type + " is not a subtype of " + resolvedHolder.type;
@@ -342,14 +346,23 @@
         // If the resolved reference is private there is no dispatch.
         // This is assuming that the method is accessible, which implies self/nest access.
         // Only include if the target has code or is native.
+        boolean isIncomplete =
+            pinnedPredicate.isPinned(resolvedHolder.type)
+                && pinnedPredicate.isPinned(resolvedMethod.method);
         return LookupResult.createResult(
-            Collections.singleton(resolvedMethod), LookupResultCollectionState.Complete);
+            Collections.singleton(resolvedMethod),
+            isIncomplete
+                ? LookupResultCollectionState.Incomplete
+                : LookupResultCollectionState.Complete);
       }
       assert resolvedMethod.isNonPrivateVirtualMethod();
       Set<DexEncodedMethod> result = Sets.newIdentityHashSet();
+      LookupCompletenessHelper incompleteness = new LookupCompletenessHelper(pinnedPredicate);
+      // TODO(b/150171154): Use instantiationHolder below.
       instantiatedInfo.forEachInstantiatedSubType(
           resolvedHolder.type,
           subClass -> {
+            incompleteness.checkClass(subClass);
             DexClassAndMethod dexClassAndMethod =
                 lookupVirtualDispatchTarget(subClass, appView, resolvedHolder.type);
             if (dexClassAndMethod != null) {
@@ -361,7 +374,8 @@
             // TODO(b/148769279): We need to look at the call site to see if it overrides
             //   the resolved method or not.
           });
-      return LookupResult.createResult(result, LookupResultCollectionState.Complete);
+      return LookupResult.createResult(
+          result, incompleteness.computeCollectionState(resolvedMethod.method, appView));
     }
 
     private static void addVirtualDispatchTarget(
@@ -584,7 +598,8 @@
     public LookupResult lookupVirtualDispatchTargets(
         DexProgramClass context,
         AppView<? extends AppInfoWithClassHierarchy> appView,
-        InstantiatedSubTypeInfo instantiatedInfo) {
+        InstantiatedSubTypeInfo instantiatedInfo,
+        PinnedPredicate pinnedPredicate) {
       return LookupResult.getIncompleteEmptyResult();
     }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 1b481d1..4d8b108 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2178,7 +2178,7 @@
     LookupResult lookupResult =
         // TODO(b/140214802): Call on the resolution once proper resolution and lookup is resolved.
         new SingleResolutionResult(holder, resolution.holder, resolution.method)
-            .lookupVirtualDispatchTargets(context, appView, appInfo);
+            .lookupVirtualDispatchTargets(context, appView, appInfo, pinnedItems::contains);
     if (!lookupResult.isLookupResultSuccess()) {
       return;
     }
diff --git a/src/main/java/com/android/tools/r8/utils/WorkList.java b/src/main/java/com/android/tools/r8/utils/WorkList.java
index 835c528..d389826 100644
--- a/src/main/java/com/android/tools/r8/utils/WorkList.java
+++ b/src/main/java/com/android/tools/r8/utils/WorkList.java
@@ -19,8 +19,10 @@
     return new WorkList<T>(EqualityTest.IDENTITY);
   }
 
-  public WorkList() {
-    this(EqualityTest.HASH);
+  public static <T> WorkList<T> newIdentityWorkList(Iterable<T> items) {
+    WorkList<T> workList = new WorkList<>(EqualityTest.IDENTITY);
+    workList.addIfNotSeen(items);
+    return workList;
   }
 
   private WorkList(EqualityTest equalityTest) {
@@ -35,6 +37,12 @@
     items.forEach(this::addIfNotSeen);
   }
 
+  public void addIfNotSeen(T[] items) {
+    for (T item : items) {
+      addIfNotSeen(item);
+    }
+  }
+
   public void addIfNotSeen(T item) {
     if (seen.add(item)) {
       workingList.addLast(item);
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 5cc8194..12bc06c 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -600,6 +600,15 @@
 
   protected static AppView<AppInfoWithLiveness> computeAppViewWithLiveness(
       AndroidApp app, Class<?> mainClass) throws Exception {
+    return computeAppViewWithLiveness(
+        app, factory -> buildKeepRuleForClassAndMethods(mainClass, factory));
+  }
+
+  protected static AppView<AppInfoWithLiveness> computeAppViewWithLiveness(
+      AndroidApp app,
+      Function<DexItemFactory, Collection<ProguardConfigurationRule>>
+          proguardConfigurationRulesGenerator)
+      throws Exception {
     AppView<AppInfoWithSubtyping> appView = computeAppViewWithSubtyping(app);
     // Run the tree shaker to compute an instance of AppInfoWithLiveness.
     ExecutorService executor = Executors.newSingleThreadExecutor();
@@ -608,7 +617,7 @@
         new RootSetBuilder(
                 appView,
                 application,
-                buildKeepRuleForClassAndMethods(mainClass, application.dexItemFactory))
+                proguardConfigurationRulesGenerator.apply(appView.appInfo().dexItemFactory()))
             .run(executor);
     AppInfoWithLiveness appInfoWithLiveness =
         EnqueuerFactory.createForInitialTreeShaking(appView)
@@ -662,7 +671,7 @@
         ListUtils.map(formalTypes, type -> buildType(type, factory)));
   }
 
-  private static List<ProguardConfigurationRule> buildKeepRuleForClass(
+  protected static List<ProguardConfigurationRule> buildKeepRuleForClass(
       Class<?> clazz, DexItemFactory factory) {
     Builder keepRuleBuilder = ProguardKeepRule.builder();
     keepRuleBuilder.setSource("buildKeepRuleForClass " + clazz.getTypeName());
@@ -674,10 +683,10 @@
     return Collections.singletonList(keepRuleBuilder.build());
   }
 
-  private static List<ProguardConfigurationRule> buildKeepRuleForClassAndMethods(
+  protected static List<ProguardConfigurationRule> buildKeepRuleForClassAndMethods(
       Class<?> clazz, DexItemFactory factory) {
     Builder keepRuleBuilder = ProguardKeepRule.builder();
-    keepRuleBuilder.setSource("buildKeepRuleForClass " + clazz.getTypeName());
+    keepRuleBuilder.setSource("buildKeepRuleForClassAndMethods " + clazz.getTypeName());
     keepRuleBuilder.setType(ProguardKeepRuleType.KEEP);
     keepRuleBuilder.setClassNames(
         ProguardClassNameList.singletonList(
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
index 774209e..88251be 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
@@ -69,7 +69,8 @@
     // Check lookup targets with include method.
     ResolutionResult resolutionResult = appInfo().resolveMethodOnClass(clazz, method.method);
     LookupResult lookupResult =
-        resolutionResult.lookupVirtualDispatchTargets(clazz, appView, appInfo());
+        resolutionResult.lookupVirtualDispatchTargets(
+            clazz, appView, appInfo(), dexReference -> false);
     assertTrue(lookupResult.isLookupResultSuccess());
     Set<DexEncodedMethod> targets = lookupResult.asLookupResultSuccess().getMethodTargets();
     assertTrue(targets.contains(method));
@@ -79,7 +80,7 @@
     LookupResult lookupResult =
         appInfo()
             .resolveMethodOnInterface(clazz, method.method)
-            .lookupVirtualDispatchTargets(clazz, appView, appInfo());
+            .lookupVirtualDispatchTargets(clazz, appView, appInfo(), dexReference -> false);
     assertTrue(lookupResult.isLookupResultSuccess());
     Set<DexEncodedMethod> targets = lookupResult.asLookupResultSuccess().getMethodTargets();
     if (appInfo().subtypes(method.method.holder).stream()
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/KeptTargetsIncompleteLookupTest.java b/src/test/java/com/android/tools/r8/resolution/virtualtargets/KeptTargetsIncompleteLookupTest.java
new file mode 100644
index 0000000..e74a3a7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/virtualtargets/KeptTargetsIncompleteLookupTest.java
@@ -0,0 +1,380 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.virtualtargets;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.LookupResult;
+import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
+import com.android.tools.r8.graph.ResolutionResult;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.ProguardConfigurationRule;
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class KeptTargetsIncompleteLookupTest extends TestBase {
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public KeptTargetsIncompleteLookupTest(TestParameters parameters) {
+    // Empty to satisfy construction of none-runtime.
+  }
+
+  private LookupResultSuccess testLookup(Class<?> methodToBeKept) throws Exception {
+    return testLookup(B.class, methodToBeKept, methodToBeKept, A.class, C.class);
+  }
+
+  private LookupResultSuccess testLookup(
+      Class<?> initial,
+      Class<?> methodToBeKept,
+      Class<?> classToBeKept,
+      Class<?>... expectedMethodHolders)
+      throws Exception {
+    return testLookup(
+        initial,
+        methodToBeKept,
+        classToBeKept,
+        Arrays.asList(expectedMethodHolders),
+        Arrays.asList(I.class, A.class, B.class, C.class));
+  }
+
+  private LookupResultSuccess testLookup(
+      Class<?> initial,
+      Class<?> methodToBeKept,
+      Class<?> classToBeKept,
+      Collection<Class<?>> expectedMethodHolders,
+      Collection<Class<?>> classes)
+      throws Exception {
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(classes).build(),
+            factory -> {
+              List<ProguardConfigurationRule> rules = new ArrayList<>();
+              rules.addAll(buildKeepRuleForClassAndMethods(methodToBeKept, factory));
+              rules.addAll(buildKeepRuleForClass(classToBeKept, factory));
+              return rules;
+            });
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(initial, "foo", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(Unrelated.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    LookupResultSuccess lookupResultSuccess = lookupResult.asLookupResultSuccess();
+    Set<String> targets =
+        lookupResultSuccess.getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    Set<String> expected =
+        expectedMethodHolders.stream()
+            .map(c -> c.getTypeName() + ".foo")
+            .collect(Collectors.toSet());
+    assertEquals(expected, targets);
+    return lookupResultSuccess;
+  }
+
+  @Test
+  public void testCompleteLookupResultWhenKeepingUnrelated() throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // B extends A { } <-- initial
+    //
+    // C extends B {
+    //   foo()
+    // }
+    assertTrue(
+        testLookup(B.class, Unrelated.class, Unrelated.class, A.class, C.class).isComplete());
+  }
+
+  @Test
+  public void testKeptResolvedAndNoKeepInSubtreeFromInitial() throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- kept, resolved
+    // }
+    //
+    // B extends A { } <-- initial
+    //
+    // C extends B {
+    //   foo()
+    // }
+    assertTrue(testLookup(A.class).isComplete());
+  }
+
+  @Test
+  public void testIncompleteLookupResultWhenKeepingStaticReceiver() throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // B extends A { } <-- initial, kept
+    //
+    // C extends B {
+    //   foo()
+    // }
+    assertTrue(testLookup(B.class).isIncomplete());
+  }
+
+  @Test
+  public void testIncompleteLookupResultWhenKeepingSubTypeMethod() throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // B extends A { } <-- initial
+    //
+    // C extends B {
+    //   foo() <-- kept
+    // }
+    assertTrue(testLookup(C.class).isIncomplete());
+  }
+
+  @Test
+  public void testIncompleteLookupResultWhenKeepingMethodOnParentToResolveAndKeepClass()
+      throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- kept
+    // }
+    //
+    // B extends A { }
+    //
+    // C extends B { <-- initial, resolved, kept
+    //   foo()
+    // }
+    assertTrue(testLookup(C.class, A.class, C.class, C.class).isIncomplete());
+  }
+
+  @Test
+  public void testCompleteLookupResultWhenKeepingMethodOnParentToResolveAndNotKeepClass()
+      throws Exception {
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- kept
+    // }
+    //
+    // B extends A { }
+    //
+    // C extends B { <-- initial, resolved
+    //   foo()
+    // }
+    assertTrue(testLookup(C.class, A.class, Unrelated.class, C.class).isComplete());
+  }
+
+  @Test
+  public void testLibraryWithNoOverride() throws Exception {
+    // ----- Library -----
+    // I {
+    //   foo()
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // ----- Program -----
+    // B extends A { } <-- initial
+    AppView<AppInfoWithSubtyping> appView =
+        computeAppViewWithSubtyping(
+            buildClasses(Collections.singletonList(B.class), Arrays.asList(A.class, I.class))
+                .build());
+    AppInfoWithSubtyping appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(B.class, "foo", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexType typeB = buildType(B.class, appInfo.dexItemFactory());
+    DexProgramClass classB = appInfo.definitionForProgramType(typeB);
+    LookupResult lookupResult =
+        resolutionResult.lookupVirtualDispatchTargets(
+            classB,
+            appView,
+            (type, subTypeConsumer, callSiteConsumer) -> {
+              if (type == typeB) {
+                subTypeConsumer.accept(classB);
+              }
+            },
+            reference -> false);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    LookupResultSuccess lookupResultSuccess = lookupResult.asLookupResultSuccess();
+    Set<String> targets =
+        lookupResultSuccess.getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    Set<String> expected = ImmutableSet.of(A.class.getTypeName() + ".foo");
+    assertEquals(expected, targets);
+    assertTrue(lookupResultSuccess.isComplete());
+  }
+
+  @Test
+  public void testPrivateKeep() throws Exception {
+    // Unrelated { <-- kept
+    //   private foo() <-- kept
+    // }
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(buildClasses(Unrelated.class).build(), Unrelated.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(Unrelated.class, "foo", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(Unrelated.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    LookupResultSuccess lookupResultSuccess = lookupResult.asLookupResultSuccess();
+    Set<String> targets =
+        lookupResultSuccess.getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    Set<String> expected = ImmutableSet.of(Unrelated.class.getTypeName() + ".foo");
+    assertEquals(expected, targets);
+    assertTrue(lookupResultSuccess.isIncomplete());
+  }
+
+  @Test
+  public void testInterfaceKept() throws Exception {
+    // I {
+    //   foo() <-- kept
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // B extends A { } <-- initial, kept
+    //
+    // C extends B {
+    //   foo()
+    // }
+    assertTrue(testLookup(B.class, I.class, B.class, A.class, C.class).isIncomplete());
+  }
+
+  @Test
+  public void testInterfaceKeptWithoutKeepInLookup() throws Exception {
+    // I {
+    //   foo() <-- kept
+    // }
+    //
+    // A implements I {
+    //   foo() <-- resolved
+    // }
+    //
+    // B extends A { } <-- initial
+    //
+    // C extends B {
+    //   foo()
+    // }
+    assertTrue(testLookup(B.class, I.class, Unrelated.class, A.class, C.class).isComplete());
+  }
+
+  @Test
+  public void testInterfaceKeptAndImplementedInSupType() throws Exception {
+    // X {
+    //   foo() <-- resolved
+    // }
+    //
+    // I {
+    //   foo() <-- kept
+    // }
+    //
+    // Y extends X implements I { } <-- initial
+    //
+    // Z extends Y { } <-- kept
+    assertTrue(
+        testLookup(
+                Y.class,
+                I.class,
+                Z.class,
+                Collections.singleton(X.class),
+                Arrays.asList(X.class, I.class, Y.class, Z.class))
+            .isIncomplete());
+  }
+
+  // TODO(b/148769279): We need to look at the call site to see if it overrides
+  //   a method that is kept.
+
+  public static class Unrelated {
+
+    private void foo() {
+      System.out.println("Unrelated.foo");
+    }
+  }
+
+  public interface I {
+    void foo();
+  }
+
+  public static class A implements I {
+    @Override
+    public void foo() {
+      System.out.println("A.foo");
+    }
+  }
+
+  public static class B extends A {}
+
+  public static class C extends B {
+    @Override
+    public void foo() {
+      System.out.println("C.foo");
+    }
+  }
+
+  public static class X {
+
+    public void foo() {
+      System.out.println("X.foo");
+    }
+  }
+
+  public static class Y extends X implements I {}
+
+  public static class Z extends Y {}
+}