Actions
Export to: EndNote  Zotero  Mendeley
Collections
This file is not currently in any collections.
Computing small pivotminors [software] Open Access
A graph G contains a graph H as a pivotminor if H can be obtained from G by applying a sequence of vertex deletions and edge pivots. Pivotminors play an important role in the study of rankwidth. However, so far, pivotminors 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 PivotMinor problem, which asks if a given graph G contains a given graph H as a pivotminor, is NPcomplete. If H is not part of the input, we denote the problem by HPivotMinor. We give a certifying polynomialtime algorithm for HPivotMinor 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 Hpivotminorfree 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 Hpivotminorfree graphs. If, for some H, the set F_H is finite, then it is possible to solve the HPivotMinorfree problem in polynomial time. In particular, this code was used to show that 2P_2pivotminorfree graphs and (2P_1+P_2)pivotminorfree graphs are characterized by a finite set of forbidden induced subgraphs.
Descriptions
 Resource type
 Software
 Contributors
 Creator:
Dabrowski, Konrad K.
^{1}
Contact person: Dabrowski, Konrad K. ^{1}
^{1} Durham University, UK
 Funder

Engineering and Physical Sciences Research Council
Leverhulme Trust
 Research methods

This Sage code was used to obtain results in the paper: "Computing Small PivotMinors" by Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, Ojoung Kwon, Sangil Oum and Daniël Paulusma, Lecture Notes in Computer Science, Proceedings of WG 2018 [forthcoming]
 Other description
 Keyword
 Pivotminors
Forbidden induced subgraphs
 Subject
 Location
 Language
 Cited in
 Identifier
 ark:/32150/r1t722h881p
doi:10.15128/r1t722h881p
 Rights
 GNU General Public Licence 2 or later (GPL2.0)
 Publisher

Durham University
 Date Created
File Details
 Depositor
 K.K. Dabrowski
 Date Uploaded
 12 July 2018, 16:07:17
 Date Modified
 5 October 2018, 15:10:44
 Audit Status
 Audits have not yet been run on this file.
 Characterization

File format: zip (ZIP Format)
Mime type: application/zip
File size: 10026
Last modified: 2018:07:12 17:26:25+01:00
Filename: wg2018.zip
Original checksum: 8934c2c4444527cf518243cee6cb0d82
User Activity  Date 

User K.K. Dabrowski has updated Computing small pivotminors [computer software]  over 3 years ago 
User N. Syrotiuk has updated Computing small pivotminors [computer software]  over 3 years ago 
User N. Syrotiuk has updated Computing small pivotminors [computer software]  over 3 years ago 
User K.K. Dabrowski has updated Computing small pivotminors [computer software]  over 3 years ago 
User N. Syrotiuk has updated Computing small pivotminors [computer software]  over 3 years ago 
User K.K. Dabrowski has updated PivotMinors  over 3 years ago 
User K.K. Dabrowski has updated PivotMinors  over 3 years ago 
User K.K. Dabrowski has deposited wg2018.zip  over 3 years ago 