  A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from
$G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors
play an important role in the study of rank-width. Pivot-minors have mainly
been studied from a structural perspective. In this paper we perform the first
systematic computational complexity study of pivot-minors. We first prove that
the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor
isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the
input, we denote the problem by $H$-Pivot-Minor. We give a certifying
polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced
subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some
integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$.
Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a
pivot-minor isomorphic to $H$. To prove the above statement, we either show
that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at
most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the
above cases.
