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 H is an induced subgraph of \(P_3+tP_1\) for some integer \(t\ge 0\) ,
\(H=K_{1,t}\) for some integer \(t\ge 1\) , or
\(|V(H)|\le 4\) except when \(H \in \{K_4,C_3+P_1\}\) .
Let \(\mathcal{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 \(\mathcal{F}_H\) have at most \(c_H\) vertices, or we determine \(\mathcal{F}_H\) precisely, for each of the above cases.
