Skip to main content

Research Repository

Advanced Search

Computing small pivot-minors

Dabrowski, K. K.; Dross, F.; Jeong, J.; Kanté, M. M.; Kwon, O.; Oum, S.; Paulusma, D.

Computing small pivot-minors Thumbnail


Authors

K. K. Dabrowski

F. Dross

J. Jeong

M. M. Kanté

O. Kwon

S. Oum



Contributors

A. Brandstädt
Editor

E. Köhler
Editor

K. Meer
Editor

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. However, so far, pivot-minors have only been studied from a structural perspective. 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|V(H)|≤4 except when H∈{K4,C3+P1,4P1}H∈{K4,C3+P1,4P1}, via a structural characterization of H-pivot-minor-free graphs in terms of a set FHFH of minimal forbidden induced subgraphs.

Citation

Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany

Presentation Conference Type Conference Paper (Published)
Conference Name 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018).
Start Date Jun 27, 2018
End Date Jun 29, 2018
Acceptance Date Jul 15, 2018
Online Publication Date Sep 2, 2018
Publication Date Sep 2, 2018
Deposit Date Jul 30, 2018
Publicly Available Date Jul 31, 2018
Print ISSN 0302-9743
Pages 125-138
Series Title Lecture notes in computer science
Series Number 11159
Series ISSN 0302-9743,1611-3349
Book Title Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 ; proceedings.
ISBN 9783030002558
DOI https://doi.org/10.1007/978-3-030-00256-5_11
Public URL https://durham-repository.worktribe.com/output/1144905
Publisher URL https://www.wg2018.b-tu.de/

Files






You might also like



Downloadable Citations