Computing small pivot-minors

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

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/