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. ¹
Contact person: Dabrowski, Konrad K. ¹

¹ 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

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