Skip to Content
No preview available


Download Analytics Citations

Export to: EndNote  |  Zotero  |  Mendeley


This file is not currently in any collections.

Computing small pivot-minors [software] Open Access

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. However, so far, pivot-minors have only been studied from a structural perspective. In the associated paper, we initiate a systematic study into their complexity aspects. We first prove that the Pivot-Minor problem, which asks if a given graph G contains a given graph H as a pivot-minor, 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 for every graph H with |V(H)|<= 4 except when H \in {K_4,C_3+P_1,4P_1}, via a structural characterization of H-pivot-minor-free graphs in terms of a set F_H of minimal forbidden induced subgraphs. Given a graph H, this Sage code calculates the set F_H of minimal forbidden induced subgraphs characterizing the class of H-pivot-minor-free graphs. If, for some H, the set F_H is finite, then it is possible to solve the H-Pivot-Minor-free problem in polynomial time. In particular, this code was used to show that 2P_2-pivot-minor-free graphs and (2P_1+P_2)-pivot-minor-free graphs are characterized by a finite set of forbidden induced subgraphs.


Resource type
Creator: Dabrowski, Konrad K. 1
Contact person: Dabrowski, Konrad K. 1
1 Durham University, UK
Engineering and Physical Sciences Research Council
Leverhulme Trust
Research methods
This Sage code was used to obtain results in the paper: "Computing Small Pivot-Minors" by Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum and Daniël Paulusma, Lecture Notes in Computer Science, Proceedings of WG 2018 [forthcoming]
Other description
Forbidden induced subgraphs
Cited in
GNU General Public Licence 2 or later (GPL-2.0)

Durham University
Date Created

File Details

K.K. Dabrowski
Date Uploaded
Date Modified
5 October 2018, 15:10:44
Audit Status
Audits have not yet been run on this file.
File format: zip (ZIP Format)
Mime type: application/zip
File size: 10026
Last modified: 2018:07:12 17:26:25+01:00
Original checksum: 8934c2c4444527cf518243cee6cb0d82
Activity of users you follow
User Activity Date
User N. Syrotiuk has updated Computing small pivot-minors [software] over 2 years ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] almost 3 years ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] almost 3 years ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] almost 3 years ago