R. Belmonte
Finding contractions and induced minors in chordal graphs via disjoint paths
Belmonte, R.; Golovach, P. A.; Heggernes, P.; Hof van 't, P.; Kaminski, M.; Paulusma, D.
Authors
P. A. Golovach
P. Heggernes
P. Hof van 't
M. Kaminski
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Contributors
T. Asano
Editor
S. Nakano
Editor
Y. Okamoto
Editor
O. Watanabe
Editor
Abstract
The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of this problem, where the vertices of P i must belong to a specified vertex subset U i for i = 1,…,k. In contrast to the original problem, which is polynomial-time solvable for any fixed integer k, we show that this variant is NP-complete even for k = 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer k if the input graph is chordal. We use this result to show that, for any fixed graph H, the problems H-Contractibility and H-Induced Minor can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph G contains H as a contraction or as an induced minor, respectively.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 22nd International Symposium on Algorithms and Computation, ISAAC 2011 |
Publication Date | Jan 1, 2011 |
Deposit Date | Dec 6, 2011 |
Pages | 110-119 |
Series Title | Lecture notes in computer science |
Series Number | 7074 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings. |
ISBN | 9783642255908 |
DOI | https://doi.org/10.1007/978-3-642-25591-5_13 |
Public URL | https://durham-repository.worktribe.com/output/1158711 |
You might also like
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
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