Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Graphs of small rank-width are pivot-minors of graphs of small tree-widthDiscrete Applied Mathematics, 2014
- On graphs with no induced subdivision ofJournal of Combinatorial Theory, Series B, 2012
- Detecting induced subgraphsDiscrete Applied Mathematics, 2009
- Circle graph obstructions under pivotingJournal of Graph Theory, 2009
- Vertex-minors, monadic second-order logic, and a conjecture by SeeseJournal of Combinatorial Theory, Series B, 2007
- The complexity of induced minors and related problemsAlgorithmica, 1995
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Circle Graph ObstructionsJournal of Combinatorial Theory, Series B, 1994
- On the complexity of finding iso- and other morphisms for partial k-treesDiscrete Mathematics, 1992
- Complement reducible graphsDiscrete Applied Mathematics, 1981