Few Induced Disjoint Paths for H-Free Graphs

Barnaby Martin*, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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. 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.
Original languageEnglish
Title of host publicationCombinatorial Optimization - 7th International Symposium, ISCO 2022, Virtual Event, May 18-20, 2022, Revised Selected Papers
EditorsIvana Ljubić, Francisco Barahona, Santanu S. Dey, A. Ridha Mahjoub
PublisherSpringer
Pages89-101
Number of pages13
ISBN (Electronic)978-3-031-18530-4
ISBN (Print)978-3-031-18529-8
DOIs
Publication statusPublished - 2022

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13526
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Induced disjoint paths
  • H-free graph
  • Complexity
  • dichotomy

Fingerprint

Dive into the research topics of 'Few Induced Disjoint Paths for H-Free Graphs'. Together they form a unique fingerprint.

Cite this