I've hit the same problem when listing dependencies for package tomcat8, which depends on tomcat8-common, which depends on "default-jre-headless | java8-runtime-headless | java8-runtime, libtomcat8-java" but java8-runtime-headless is not shown:
# apt-rdepends --state-follow=Installed --state-show=Installed tomcat8 tomcat8 Depends: tomcat8-common (>= 8.5.38-2) ... tomcat8-common Depends: libtomcat8-java (>= 8.5.38-2) # apt-cache showpkg java8-runtime-headless ... Reverse Provides: openjdk-8-jre-headless 8u212-b01-1~deb9u1 (= ) openjdk-11-jre-headless 11.0.3+1-1~bpo9+1 (= ) openjdk-8-jre-headless 8u181-b13-2~deb9u1 (= ) default-jre-headless 2:1.8-58 (= ) openjdk-11-jre-headless 11.0.3+1-1 (= ) default-jre-headless 2:1.11-71 (= ) -- With best regards, Dmitry