Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Martin, B.; Paulusma, D.; Smith, S.; van Leeuwen, E.J.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
S. Smith
E.J. van Leeuwen
Abstract
Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. This is a classical graph problem that is NP-complete even for k=2. We introduce a natural generalization, INDUCED DISJOINT CONNECTED SUBGRAPHS: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.
Citation
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Presentation Conference Type | Conference Paper (Published) |
---|---|
Acceptance Date | Jul 15, 2022 |
Online Publication Date | Oct 1, 2022 |
Publication Date | 2022 |
Deposit Date | Oct 16, 2022 |
Publicly Available Date | Oct 2, 2023 |
Print ISSN | 0302-9743 |
Publisher | Springer Verlag |
Volume | 13453 |
Pages | 398-411 |
Series Title | Lecture Notes in Computer Science |
Series ISSN | 0302-9743 |
Book Title | Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers |
ISBN | 9783031159138 |
DOI | https://doi.org/10.1007/978-3-031-15914-5_29 |
Public URL | https://durham-repository.worktribe.com/output/1643993 |
Files
Accepted Book Chapter
(405 Kb)
PDF
Copyright Statement
The final authenticated version is available online at https://doi.org/10.1007/978-3-031-15914-5_29
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Matching cuts in graphs of high girth and H-free graphs
(2023)
Presentation / Conference Contribution
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
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