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). Computing small pivot-minors. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 ; proceedings (125-138). https://doi.org/10.1007/978-3-030-00256-5_11

Conference Name 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018).
Conference Location Cottbus, Germany
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 Mar 29, 2024
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