| Autor: |
Martin, Barnaby, Paulusma, Daniël, Smith, Siani, van Leeuwen, Erik Jan, Ljubić, Ivana, Barahona, Francisco, Dey, Santanu S., Mahjoub, A. Ridha |
| Přispěvatelé: |
Sub Algorithms and Complexity, Algorithms and Complexity |
| Jazyk: |
angličtina |
| Rok vydání: |
2022 |
| Předmět: |
|
| Popis: |
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. For a fixed integer k, the k-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. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-INDUCED DISJOINT PATHS is NP-complete. We prove new complexity results for k-INDUCED DISJOINT PATHS if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for INDUCED DISJOINT PATHS, the variant where k is part of the input. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
