Disjoint paths in tournaments

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1016/j.aim.2014.11.011

Disjoint paths in tournaments

Maria Chudnovsky, Alex Scott, Paul Seymour

Mathematics

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

15 Scopus citations

Abstract

Given k pairs of vertices (s_i, t_i) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from s_i to t_i for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

Original language	English (US)
Pages (from-to)	582-597
Number of pages	16
Journal	Advances in Mathematics
Volume	270
DOIs	https://doi.org/10.1016/j.aim.2014.11.011
State	Published - Jan 2 2015

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Disjoint paths
Dynamic programming
Graph
Routing
Tournament

Access to Document

10.1016/j.aim.2014.11.011

Cite this

@article{d9257f6c1500459780376ffd22babaa7,

title = "Disjoint paths in tournaments",

abstract = "Given k pairs of vertices (si, ti) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.",

keywords = "Disjoint paths, Dynamic programming, Graph, Routing, Tournament",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour",

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

year = "2015",

month = jan,

day = "2",

doi = "10.1016/j.aim.2014.11.011",

language = "English (US)",

volume = "270",

pages = "582--597",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Disjoint paths in tournaments

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

PY - 2015/1/2

Y1 - 2015/1/2

N2 - Given k pairs of vertices (si, ti) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

AB - Given k pairs of vertices (si, ti) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

KW - Disjoint paths

KW - Dynamic programming

KW - Graph

KW - Routing

KW - Tournament

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

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

U2 - 10.1016/j.aim.2014.11.011

DO - 10.1016/j.aim.2014.11.011

M3 - Article

AN - SCOPUS:84913533928

SN - 0001-8708

VL - 270

SP - 582

EP - 597

JO - Advances in Mathematics

JF - Advances in Mathematics

ER -

Disjoint paths in tournaments

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this