Disjoint paths and connected subgraphs for H-free graphs
| Autor: | Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity |
|---|---|
| Přispěvatelé: | Sub Algorithms and Complexity, Algorithms and Complexity |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Class (set theory) Discrete Mathematics (cs.DM) General Computer Science H-free graph Disjoint sets Computational Complexity (cs.CC) Graph Theoretical Computer Science Combinatorics Set (abstract data type) Computer Science - Computational Complexity Terminal (electronics) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science - Data Structures and Algorithms FOS: Mathematics Complexity dichotomy Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Disjoint paths Computer Science - Discrete Mathematics Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Computer Science(all) |
| Zdroj: | Theoretical computer science, 2022, Vol.898, pp.59-68 [Peer Reviewed Journal] IWOCA Theoretical Computer Science, 898, 59. Elsevier |
| ISSN: | 0304-3975 |
| Popis: | The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k-Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths. Moreover, we give exact algorithms for Disjoint Paths and Disjoint Connected Subgraphs on graphs with n vertices and m edges that have running times of O(2nn 2 k) and O(3n km), respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect