Skip to Content
No preview available

Actions

Download Analytics Citations

Export to: EndNote  |  Zotero  |  Mendeley

Collections

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.

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 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
Keyword
Pivot-minors
Forbidden induced subgraphs
Subject
Location
Language
Cited in
Identifier
ark:/32150/r1t722h881p
doi:10.15128/r1t722h881p
Rights
GNU General Public Licence 2 or later (GPL-2.0)

Publisher
Durham University
Date Created

File Details

Depositor
K.K. Dabrowski
Date Uploaded
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
Activity of users you follow
User Activity Date
User K.K. Dabrowski has updated Computing small pivot-minors [computer software] 3 months ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] 3 months ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] 3 months ago
User K.K. Dabrowski has updated Computing small pivot-minors [computer software] 3 months ago
User N. Syrotiuk has updated Computing small pivot-minors [computer software] 3 months ago
User K.K. Dabrowski has updated Pivot-Minors 3 months ago
User K.K. Dabrowski has updated Pivot-Minors 3 months ago
User K.K. Dabrowski has deposited wg2018.zip 3 months ago