  We study conditions that ensure uniqueness theorems of Cuntz-Krieger type for
relative Cuntz-Pimsner algebras $\mathcal{O}(J,X)$ associated to a
$C^*$-correspondence $X$ over a $C^*$-algebra $A$. We give general sufficient
conditions phrased in terms of a multivalued map $\widehat{X}$ acting on the
spectrum $\widehat{A}$ of $A$. When $X(J)$ is of Type I we construct a directed
graph dual to $X$ and prove a uniqueness theorem using this graph. When $X(J)$
is liminal, we show that topological freeness of this graph is equivalent to
the uniqueness property for $\mathcal{O}(J,X)$, as well as to an algebraic
condition, which we call $J$-acyclicity of $X$.
  As an application we improve the Fowler-Raeburn uniqueness theorem for the
Toeplitz algebra $\mathcal{T}_X$. We give new simplicity criteria for
$\mathcal{O}_X$. We generalize and enhance uniqueness results for relative
quiver $C^*$-algebras of Muhly and Tomforde. We also discuss applications to
crossed products by endomorphisms.
