Induced Disjoint Paths in AT-free graphs

Petr A. Golovach; Daniël Paulusma; Erik Jan van Leeuwen

doi:10.1016/j.jcss.2021.10.003

Induced Disjoint Paths in AT-free graphs

Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Paths P₁,…,P_k are mutually induced if any two distinct P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (s_i,t_i) contains k mutually induced paths P_i such that each P_i connects s_i and t_i. This problem is NP-complete even for k=2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter |V_H|, even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-IN-A-PATH and k-IN-A-TREE are polynomial-time solvable on AT-free graphs even if k is part of the input.

Original language	English
Pages (from-to)	170-191
Number of pages	22
Journal	Journal of Computer and System Sciences
Volume	124
DOIs	https://doi.org/10.1016/j.jcss.2021.10.003
Publication status	Published - Mar 2022

Bibliographical note

Publisher Copyright:
© 2021 Elsevier Inc.

Funding

This work is supported by EPSRC ( EP/G043434/1 ), Royal Society ( JP100692 ), the European Research Council (ERC) via the grant Rigorous Theory of Preprocessing (reference 267959 ), and ERC StG project PAAl no. 259515 . A preliminary abstract of this paper appeared in the proceedings of SWAT 2012 [14] .

Funders	Funder number
Engineering and Physical Sciences Research Council	EP/G043434/1
Royal Society	JP100692
European Research Council	259515, 267959

Keywords

AT-free graph
Co-bipartite graph
Disjoint paths
Induced topological minor
Polynomial-time algorithm
W[1]-hardness
k-in-a-Path
k-in-a-Tree

Access to Document

10.1016/j.jcss.2021.10.003

1-s2.0-S0022000021001008-mainFinal published version, 714 KBLicence: Taverne

Cite this

@article{7fa9913cdf76408e8a990ae79a41deca,

title = "Induced Disjoint Paths in AT-free graphs",

abstract = "Paths P1,…,Pk are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-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 connects si and ti. This problem is NP-complete even for k=2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter |VH|, even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-IN-A-PATH and k-IN-A-TREE are polynomial-time solvable on AT-free graphs even if k is part of the input.",

keywords = "AT-free graph, Co-bipartite graph, Disjoint paths, Induced topological minor, Polynomial-time algorithm, W[1]-hardness, k-in-a-Path, k-in-a-Tree",

author = "Golovach, {Petr A.} and Dani{\"e}l Paulusma and Leeuwen, {Erik Jan van}",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier Inc.",

year = "2022",

month = mar,

doi = "10.1016/j.jcss.2021.10.003",

language = "English",

volume = "124",

pages = "170--191",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Induced Disjoint Paths in AT-free graphs

AU - Golovach, Petr A.

AU - Paulusma, Daniël

AU - Leeuwen, Erik Jan van

PY - 2022/3

Y1 - 2022/3

N2 - Paths P1,…,Pk are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-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 connects si and ti. This problem is NP-complete even for k=2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter |VH|, even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-IN-A-PATH and k-IN-A-TREE are polynomial-time solvable on AT-free graphs even if k is part of the input.

AB - Paths P1,…,Pk are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-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 connects si and ti. This problem is NP-complete even for k=2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter |VH|, even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-IN-A-PATH and k-IN-A-TREE are polynomial-time solvable on AT-free graphs even if k is part of the input.

KW - AT-free graph

KW - Co-bipartite graph

KW - Disjoint paths

KW - Induced topological minor

KW - Polynomial-time algorithm

KW - W[1]-hardness

KW - k-in-a-Path

KW - k-in-a-Tree

UR - http://www.scopus.com/inward/record.url?scp=85118479979&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2021.10.003

DO - 10.1016/j.jcss.2021.10.003

M3 - Article

SN - 0022-0000

VL - 124

SP - 170

EP - 191

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Induced Disjoint Paths in AT-free graphs

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this