K.K. Dabrowski
Contracting Bipartite Graphs to Paths and Cycles
Dabrowski, K.K.; Paulusma, D.
Abstract
Testing if a given graph G contains the k -vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. However, the situation changes for the problem of checking if a graph can be modified into Pk by using only edge contractions. In this case the problem is known to be NP-complete even if k=4. This led to an intensive investigation for testing contractibility on restricted graph classes. We focus on bipartite graphs. Heggernes, van 't Hof, Lévêque and Paul proved that the problem stays NP-complete for bipartite graphs if k=6. We strengthen their result from k=6 to k=5. We also show that the problem of contracting a bipartite graph to the 6-vertex cycle C6 is NP-complete. The cyclicity of a graph is the length of the longest cycle the graph can be contracted to. As a consequence of our second result, determining the cyclicity of a bipartite graph is NP-hard.
Citation
Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 29, 2017 |
Online Publication Date | Jul 5, 2017 |
Publication Date | Nov 1, 2017 |
Deposit Date | Jun 30, 2017 |
Publicly Available Date | Mar 28, 2024 |
Journal | Information Processing Letters |
Print ISSN | 0020-0190 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 127 |
Pages | 37-42 |
DOI | https://doi.org/10.1016/j.ipl.2017.06.013 |
Public URL | https://durham-repository.worktribe.com/output/1384022 |
Files
Accepted Journal Article
(364 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© 2017 The Author(s). Published by Elsevier B.V. This is an open access article under the
CC BY license (http://creativecommons.org/licenses/by/4.0/).
You may copy and distribute the article, create extracts, abstracts and new works from the article, alter and revise the article, text or data mine the article and otherwise reuse the article commercially (including reuse and/or resale of the article) without permission from Elsevier. You must give appropriate credit to the original work, together with a link to the formal publication through the relevant DOI and a link to the Creative Commons user license above. You must indicate if any changes are made but not in any way that suggests the licensor endorses you or your use of the work.
Published Journal Article
(296 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search