Dabrowski, K.K. and Dross, F. and Jeong, J. and Kanté, M.M. and Kwon, O. and Oum, S. and Paulusma, D. (2018) 'Computing small pivot-minors.', in Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 ; proceedings. Cham, Switzerland: Springer, pp. 125-138. Lecture notes in computer science. (11159).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (448Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1007/978-3-030-00256-5_11 |
| Publisher statement: | The final publication is available at Springer via https://doi.org/10.1007/978-3-030-00256-5_11 |
| Date accepted: | 15 July 2018 |
| Date deposited: | 31 July 2018 |
| Date of first online publication: | 02 September 2018 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
